/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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
出力
答えを出力せよ。
入力例 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 で割った余りを求めてください。
Score : 600 points
Problem Statement
Among the sequences of length K consisting of integers, A=(A_1, \ldots, A_K), how many satisfy all of the conditions below?
Find the count modulo 998244353.
-
0\leq A_i \leq M-1 for every i(1\leq i\leq K).
-
\displaystyle\prod_{i=1}^{K} A_i \equiv N \pmod M.
Constraints
- 1 \leq K \leq 10^9
- 0 \leq N \lt M \leq 10^{12}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
K N M
Output
Print the answer.
Sample Input 1
2 3 6
Sample Output 1
5
The five sequences A satisfying the conditions are (1,3),(3,1),(3,3),(3,5),(5,3).
Sample Input 2
10 0 2
Sample Output 2
1023
Sample Input 3
1000000000 20220326 1000000000000
Sample Output 3
561382653
Be sure to find the count modulo 998244353.