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$
.
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)$
.
Print the value of $S$
modulo $998,244,353$
.
Input | Output |
---|---|
4 1 2 | 16 |
Here, |
Input | Output |
---|---|
1000000000 69 6969 | 888406388 |