题目描述
定义 $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
输出
10
样例 2
输入
5 1 4
输出
1300
样例 3
输入
1 9 19
输出
13123110
样例 4
输入
114 514 1919810
输出
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$ |