一個非負整數集合是好的，若且唯若集合中的所有數都小於 $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 \cdot 2 \cdot 2 = 8$。

第二個範例中，$\{0,1,\ldots,19\}$ 的任意子集都是好的，因此答案是 $2^{20}=1\,048\,576$。