Определим $f_0(x) = x^n$ и $f_m(x) = \sum_{i=0}^x f_{m-1}(i)$.
Даны $n, m, x$. Найдите $f_m(x)$ по модулю $998244353$.
Входные данные
На вход подаются $n, m, x$.
Выходные данные
Выведите $f_m(x) \bmod 998244353$.
Примеры
Пример 1
1 1 4
Выход 1
10
Пример 2
5 1 4
Выход 2
1300
Пример 3
1 9 19
Выход 3
13123110
Пример 4
114 514 1919810
Выход 4
693970832
Ограничения
Для $100\%$ данных гарантируется, что $1\le n\le 10^7; 1\le m,x\le 4\times 10^8$.
| Номер теста | $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$ |