問題文

長さ $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$

出力

答えを出力せよ。

入力例 1

2 3 6

出力例 1

5

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

入力例 2

10 0 2

出力例 2

1023

入力例 3

1000000000 20220326 1000000000000

出力例 3

561382653

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