Sinulle annetaan pituuden $N$ merkkijono $S$, joka koostuu numeroista $1, 2, \dots, 9$.
Tarkastellaan kolmiomaista pyramidia, joka koostuu yhteensä $\frac{N(N+1)}{2}$ palikasta.
Pyramidi on jaettu $N$ kerrokseen, jotka on numeroitu $1, 2, \dots, N$ ylhäältä alas. Kerros $i$ ($1 \le i \le N$) sisältää $i$ palikkaa järjestettynä yhteen vaakasuoraan riviin vasemmalta oikealle. Jokaiseen palikkaan on kirjoitettu merkkijono. Merkitään $C_{i,j}$:llä merkkijonoa, joka on kirjoitettu kerroksen $i$ vasemmalta lukien $j$-nteen palikkaan ($1 \le j \le i$).
Merkkijonot $C_{i,j}$ toteuttavat seuraavat ehdot:
- Jos $i = N$, niin $C_{i,j}$ on pituuden $1$ merkkijono, joka koostuu merkkijonon $S$ $j$-nnestä merkistä.
- Jos $1 \le i < N$, niin $C_{i,j}$ saadaan yhdistämällä (konkatenoimalla) merkkijonot $C_{i+1,j}$ ja $C_{i+1,j+1}$ tässä järjestyksessä.
Tulkitse $C_{1,1}$ kymmenjärjestelmän kokonaisluvuksi ja laske sen arvo modulo $998244353$.
Syöte
Syöte annetaan seuraavassa muodossa:
N S
- $N$ on kokonaisluku.
- $1 \le N \le 2 \times 10^5$.
- $S$ on pituuden $N$ merkkijono, joka koostuu numeroista $1, 2, \dots, 9$.
Tuloste
Tulosta vastaus.
Esimerkit
Syöte 1
4 8192
Tuloste 1
81191992
Syöte 2
1 5
Tuloste 2
5
Syöte 3
14 11123455678999
Tuloste 3
913063116
Huomautus
Ensimmäisessä esimerkissä $S = 8192$. Kun pyramidi rakennetaan sääntöjen mukaisesti, saadaan $C_{1,1} = 81191992$.
Toisessa esimerkissä $S = 5$. Pyramidi koostuu vain yhdestä palikasta ja $C_{1,1} = 5$.