9600: ABC245 —— Ex - Product Modulo 2
[Creator : ]
Description
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$.
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$.
Input
Input is given from Standard Input in the following format:
```
$K$ $N$ $M$
```
```
$K$ $N$ $M$
```
Output
Print the answer.
Constraints
- $1 \leq K \leq 10^9$
- $0 \leq N \lt M \leq 10^{12}$
- All values in input are integers.
- $0 \leq N \lt M \leq 10^{12}$
- All values in input are integers.
Sample 1 Input
2 3 6
Sample 1 Output
5
The five sequences A satisfying the conditions are (1,3),(3,1),(3,3),(3,5),(5,3).
Sample 2 Input
10 0 2
Sample 2 Output
1023
Sample 3 Input
1000000000 20220326 1000000000000
Sample 3 Output
561382653