分数: 600 点
问题陈述
长度序列之中 K 由整数组成, A=(A_1, \ldots, A_K),有多少满足以下所有条件?
求计数模数 998244353.
-
0\leq A_i \leq M-1 对于每个 i(1\leq i\leq K).
-
\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).
示例输入 2
10 0 2
示例输出 2
1023
示例输入 3
1000000000 20220326 1000000000000
示例输出 3
561382653
一定要找到计数模数 998244353.