乘积取模

题目描述

在长度为 $K$ 的整数序列 $A=(A_1,\ldots,A_K)$ 中,有多少个满足以下所有条件?

求个数对 $998244353$ 取模。

• 对所有 $i(1\le i\le K)$,有 $0\le A_i\le M-1$。
• 有 $\displaystyle\prod_{i=1}^{K} A_i \equiv N \pmod M$。

输入格式

输入按以下格式从标准输入给出:

K N M

输出格式

输出答案。

样例

2 3 6

5

满足条件的 5 个序列 $A$ 为 $(1,3),(3,1),(3,3),(3,5),(5,3)$。

10 0 2

1023

1000000000 20220326 1000000000000

561382653

请务必输出对 $998244353$ 取模后的答案。

数据范围

• $1 \le K \le 10^9$
• $0 \le N \lt M \le 10^{12}$
• 输入中的所有值均为整数。