一個由非負整數組成嘅集合，當且僅當集合入面所有數都小於 $T$，而且佢哋嘅總和對 $n$ 取模同 $rem$ 同餘，就稱為好集合。你嘅任務係搵出唔同好集合嘅數目。

輸入

輸入第一行包含以空格分隔嘅整數 $n$ 同 $rem$（$0 \le rem < n \le 10^4$）。輸入第二行包含一個整數 $T$（$1 \le T \le 10^{100\,000}-1$）。

輸出

輸出唔同好集合嘅數目。由於呢個數可能非常大，你應該輸出佢對質數 $998\,244\,353$ 取模嘅結果。

樣例

輸入 1

3 2
5

輸出 1

8

輸入 2

1 0
20

輸出 2

1048576

說明

第一個樣例入面，我哋可以自由選擇加入或者唔加入 $0$ 同 $3$，因為咁樣唔會改變餘數。喺 $\{1,2,4\}$ 當中，有兩個好集合：$\{2\}$ 同 $\{1,4\}$。所以答案係 $2\cdot2\cdot2=8$。

第二個樣例入面，$\{0,1,\ldots,19\}$ 嘅任何子集都係好集合，所以答案係 $2^{20}=1\,048\,576$。