You

Cherry isn't feeling well right now as she found a problem that she couldn't solve. So she started to listen to You and you, to make her happy, have to solve the problem for her.

You are given three integers $n, x$ and $m$.

Let $S = \sum\limits_{k \,=\, 0}^{n}{{{n}\choose{k}} \cdot x^{k \, \% \, m}}$. Here, $\%$ is the modulo operator.

You have to find the value of $S$ modulo $998,244,353$.

Input

The first and only line of the input contains three space-separated integers $n(1 \le n \le 10^{12})$, $x(1 \le x \lt 998,244,353)$ and $m(1 \le m \le 20,000)$.

Output

Print the value of $S$ modulo $998,244,353$.

Samples

Input	Output
4 1 2	16
Here, ${{4}\choose{0}} \cdot 1^{0 \, \% \, 2} + {{4}\choose{1}} \cdot 1^{1 \, \% \, 2} + {{4}\choose{2}} \cdot 1^{2 \, \% \, 2} + {{4}\choose{3}} \cdot 1^{3 \, \% \, 2} + {{4}\choose{4}} \cdot 1^{4 \, \% \, 2} = 16$

Input	Output
1000000000 69 6969	888406388