Eine Menge nichtnegativer Ganzzahlen heißt gut genau dann, wenn alle Zahlen der Menge kleiner als $T$ sind und ihre Summe modulo $n$ kongruent zu $rem$ ist. Deine Aufgabe besteht darin, die Anzahl verschiedener guter Mengen zu bestimmen.

Eingabe

Die erste Zeile der Eingabe enthält die durch Leerzeichen getrennten Ganzzahlen $n$ und $rem$ ($0 \le rem < n \le 10^4$). Die zweite Zeile der Eingabe enthält eine einzelne Ganzzahl $T$ ($1 \le T \le 10^{100\,000}-1$).

Ausgabe

Gib die Anzahl verschiedener guter Mengen aus. Da diese Zahl sehr groß sein kann, sollst du sie modulo der Primzahl $998\,244\,353$ ausgeben.

Beispiele

Eingabe 1

3 2
5

Ausgabe 1

8

Eingabe 2

1 0
20

Ausgabe 2

1048576

Hinweis

Im ersten Beispiel können wir die Zahlen $0$ und $3$ beliebig ein- oder ausschließen; dadurch ändert sich der Rest nicht. Aus den Zahlen $\{1,2,4\}$ gibt es zwei gute Mengen: $\{2\}$ und $\{1,4\}$. Die Antwort ist also $2\cdot2\cdot2=8$.

Im zweiten Beispiel ist jede Teilmenge von $\{0,1,\ldots,19\}$ gut. Daher lautet die Antwort $2^{20}=1\,048\,576$.