非負整数の集合が「よい集合」であるとは、その集合のすべての数が $T$ 未満であり、その総和が $n$ を法として $\mathrm{rem}$ と合同であることをいいます。異なるよい集合の個数を求めてください。

入力

最初の行には、空白で区切られた整数 $n$ と $\mathrm{rem}$ が与えられます（$0 \le \mathrm{rem} < n \le 10^4$）。2 行目には整数 $T$ が 1 つ与えられます（$1 \le T \le 10^{100\,000}-1$）。

出力

異なるよい集合の個数を出力してください。この数は非常に大きくなる可能性があるため、素数 $998\,244\,353$ で割った余りを出力してください。

入出力例

入力 1

3 2
5

出力 1

8

入力 2

1 0
20

出力 2

1048576

注記

1 つ目の例では、$0$ と $3$ を含めるかどうかは自由に選べます。これらは余りを変えません。$\{1,2,4\}$ の数から作れるよい集合は、$\{2\}$ と $\{1,4\}$ の 2 つです。したがって、答えは $2\cdot2\cdot2=8$ です。

2 つ目の例では、$\{0,1,\ldots,19\}$ のどの部分集合もよい集合なので、答えは $2^{20}=1\,048\,576$ です。