# 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


### Statistics

50% Solution Ratio

NirjhorEarliest, 9M ago

Deshi_TouristFastest, 0.2s

nuipqiunLightest, 1.3 MB

Deshi_TouristShortest, 2283B