Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

You

By YouKnowWho · Limits 3s, 512 MB

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

InputOutput
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$

InputOutput
1000000000 69 6969
888406388

    Discussion

    Statistics


    33% Solution Ratio

    NirjhorEarliest, 1M ago

    nuipqiunFastest, 0.3s

    nuipqiunLightest, 1.3 MB

    NirjhorShortest, 2377B

    Submit

    Login to submit