問題文
$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
制約
すべてのデータセットにおいて、$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$ |