配点 : $600$ 点

問題文

長さ $K$ の整数からなる数列 $A=(A_1,\ldots,A_K)$ のうち、以下の条件を全て満たすものは何通りありますか？ $998244353$ で割った余りを求めてください。

• すべての $i(1\leq i\leq K)$ について、$0\leq A_i \leq M-1$
• $\displaystyle\prod_{i=1}^{K} A_i \equiv N \pmod M$

制約

• $1 \leq K \leq 10^9$
• $0 \leq N \lt M \leq 10^{12}$
• 入力は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

$K$ $N$ $M$

出力

答えを出力せよ。

2 3 6

5

条件を満たす $A$ は、$(1,3),(3,1),(3,3),(3,5),(5,3)$ の $5$ つです。

10 0 2

1023

1000000000 20220326 1000000000000

561382653

$998244353$ で割った余りを求めてください。