Un ensemble d'entiers positifs ou nuls est dit convenable si et seulement si tous ses éléments sont strictement inférieurs à $T$ et si leur somme est congrue à $rem$ modulo $n$. Votre tâche consiste à déterminer le nombre d'ensembles convenables distincts.

Entrée

La première ligne de l'entrée contient les entiers $n$ et $rem$, séparés par un espace ($0 \le rem < n \le 10^4$). La deuxième ligne contient un entier $T$ ($1 \le T \le 10^{100\,000}-1$).

Sortie

Affichez le nombre d'ensembles convenables distincts. Ce nombre pouvant être très grand, affichez-le modulo le nombre premier $998\,244\,353$.

Exemples

Entrée 1

3 2
5

Sortie 1

8

Entrée 2

1 0
20

Sortie 2

1048576

Remarque

Dans le premier exemple, on peut inclure ou exclure librement les nombres $0$ et $3$ sans changer le reste. Parmi les nombres $\{1,2,4\}$, deux ensembles sont convenables : $\{2\}$ et $\{1,4\}$. La réponse est donc $2 \cdot 2 \cdot 2 = 8$.

Dans le second exemple, tout sous-ensemble de $\{0,1,\ldots,19\}$ est convenable ; la réponse est donc $2^{20}=1\,048\,576$.