Define $f_0(x) = x^n$ and $f_m(x) = \sum_{i=0}^x f_{m-1}(i)$.
Given $n, m, x$, calculate $f_m(x)$ modulo $998244353$.
Input
Input $n, m, x$.
Output
Output $f_m(x) \bmod 998244353$.
Constraints
For $100\%$ of the data, $1\le n\le 10^7$ and $1\le m, x\le 4\times 10^8$.
| Data Point ID | $n\le$ | $m\le$ | $x\le$ |
|---|---|---|---|
| $1$ | $100$ | $100$ | $100$ |
| $2,3$ | $10^7$ | $10^7$ | $10^3$ |
| $4,5$ | $10^5$ | ||
| $6$ | $10^6$ | ||
| $7$ | $10^7$ | ||
| $8$ | $1$ | $4\times 10^8$ | |
| $9$ | $3$ | ||
| $10$ | $10^5$ | ||
| $11,12$ | $4\times 10^8$ | ||
| $13$ | $10^6$ | $10^7$ | |
| $14,15$ | $4\times 10^8$ | ||
| $16$ | $10^7$ | $1$ | |
| $17$ | $3$ | ||
| $18$ | $10^5$ | $10^5$ | |
| $19$ | $10^7$ | $10^7$ | |
| $20$ | $4\times 10^8$ |
Examples
Input 1
1 1 4
Output 1
10
Input 2
5 1 4
Output 2
1300
Input 3
1 9 19
Output 3
13123110
Input 4
114 514 1919810
Output 4
693970832