On vous donne une chaîne de caractères $S$ de longueur $N$ composée des chiffres $1, 2, \dots, 9$.
Considérons une pyramide triangulaire composée d'un total de $\frac{N(N+1)}{2}$ blocs.
La pyramide est divisée en $N$ couches, numérotées $1, 2, \dots, N$ de haut en bas. La couche $i$ ($1 \le i \le N$) contient $i$ blocs disposés sur une seule rangée horizontale de gauche à droite. Chaque bloc porte une chaîne de caractères. Soit $C_{i,j}$ la chaîne écrite sur le $j$-ème bloc en partant de la gauche ($1 \le j \le i$) dans la couche $i$.
Les chaînes $C_{i,j}$ vérifient les conditions suivantes :
- Si $i = N$, alors $C_{i,j}$ est la chaîne de longueur $1$ constituée du $j$-ème caractère de $S$.
- Si $1 \le i < N$, alors $C_{i,j}$ est la concaténation de $C_{i+1,j}$ et $C_{i+1,j+1}$, dans cet ordre.
Interprétez $C_{1,1}$ comme un entier décimal et calculez sa valeur modulo $998244353$.
Entrée
L'entrée est donnée dans le format suivant :
N S
- $N$ est un entier.
- $1 \le N \le 2 \times 10^5$.
- $S$ est une chaîne de longueur $N$ composée des chiffres $1, 2, \dots, 9$.
Sortie
Affichez la réponse.
Exemples
Entrée 1
4 8192
Sortie 1
81191992
Entrée 2
1 5
Sortie 2
5
Entrée 3
14 11123455678999
Sortie 3
913063116
Note
Dans le premier exemple, $S = 8192$. En construisant la pyramide selon les règles, nous obtenons $C_{1,1} = 81191992$.
Dans le deuxième exemple, $S = 5$. La pyramide est constituée d'un seul bloc, et $C_{1,1} = 5$.