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.