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,xn, x and mm.

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

You have to find the value of SS modulo 998,244,353998,244,353.

Input

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

Output

Print the value of SS modulo 998,244,353998,244,353.

Samples

InputOutput
4 1 2
16

Here, (40)10%2+(41)11%2+(42)12%2+(43)13%2+(44)14%2=16{{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


    50% Solution Ratio

    NirjhorEarliest, 9M ago

    Deshi_TouristFastest, 0.2s

    nuipqiunLightest, 1.3 MB

    Deshi_TouristShortest, 2283B

    Submit

    Login to submit

    Toph uses cookies. By continuing you agree to our Cookie Policy.