Meillä on merkkijono, joka koostuu $n$:stä nollasta poikkeavasta numerosta. Voimme muodostaa lausekkeen lisäämällä enintään yhden merkeistä $+$ (plus) tai $\cdot$ (kertolasku) minkä tahansa kahden peräkkäisen numeron väliin. Esimerkiksi merkkijonosta 231 voimme muodostaa yhdeksän lauseketta:

$231$, $23 + 1$, $23 \cdot 1$, $2 + 31$, $2 \cdot 31$, $2 + 3 + 1$, $2 + 3 \cdot 1$, $2 \cdot 3 + 1$, $2 \cdot 3 \cdot 1$.

Laskemme näiden lausekkeiden arvot normaalin laskujärjestyksen mukaisesti ja laskemme kaikkien arvojen summan. Esimerkissämme saamme

$$231 + 24 + 23 + 33 + 62 + 6 + 5 + 7 + 6 = 397$$

Laske yllä oleva summa modulo $10^9 + 7$.

Syöte

Syötteen ensimmäinen rivi sisältää yhden kokonaisluvun $n$ ($1 \le n \le 10^6$), joka ilmaisee merkkijonon pituuden.

Toinen rivi sisältää pituudeltaan $n$ olevan merkkijonon, joka koostuu numeroista 1–9.

Tuloste

Tulosta yksi kokonaisluku, kaikkien lausekkeiden summa modulo $10^9 + 7$.

Esimerkki

Syöte

3
231

Tuloste

397