Gefinn er strengur $S$ af lengd $N$ sem samanstendur af tölustöfunum $1, 2, \dots, 9$.
Lítum á þríhyrningslaga pýramída sem er gerður úr alls $\frac{N(N+1)}{2}$ kubbum.
Pýramídanum er skipt í $N$ lög, númeruð $1, 2, \dots, N$frá toppi til botns. Lag $i$ ($1 \le i \le N$) inniheldur $i$ kubba sem er raðað í eina lárétta röð frá vinstri til hægri. Á hvern kubb er skrifaður strengur. Látum $C_{i,j}$ tákna strenginn sem er skrifaður á $j$-ta kubbinn frá vinstri ($1 \le j \le i$) í lagi $i$.
Strengirnir $C_{i,j}$ uppfylla eftirfarandi skilyrði:
- Ef $i = N$, þá er $C_{i,j}$ strengurinn af lengd $1$ sem samanstendur af $j$-ta stafnum í $S$.
- Ef $1 \le i < N$, þá er $C_{i,j}$ samskeytingin á $C_{i+1,j}$ og $C_{i+1,j+1}$, í þessari röð.
Túlkaðu $C_{1,1}$ sem heiltölu í tugakerfi og reiknaðu gildi hennar módulo $998244353$.
Inntak
Inntakið er gefið á eftirfarandi sniði:
N S
- $N$ er heiltala.
- $1 \le N \le 2 \times 10^5$.
- $S$ er strengur af lengd $N$ sem samanstendur af tölustöfunum $1, 2, \dots, 9$.
Úttak
Prentaðu svarið.
Dæmi
Inntak 1
4 8192
Úttak 1
81191992
Inntak 2
1 5
Úttak 2
5
Inntak 3
14 11123455678999
Úttak 3
913063116
Athugasemd
Í fyrsta dæminu er $S = 8192$. Með því að byggja pýramídann samkvæmt reglunum fáum við $C_{1,1} = 81191992$.
Í öðru dæminu er $S = 5$. Pýramídinn samanstendur af einum kubbi og $C_{1,1} = 5$.