Vi har en sträng som består av $n$ nollskilda siffror. Vi kan skapa ett uttryck genom att infoga högst ett av tecknen $+$ (plus) eller $\cdot$ (gånger) mellan vilka två på varandra följande siffror som helst. Till exempel kan vi från strängen 231 skapa nio uttryck:

$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$.

Vi beräknar värdet av dessa uttryck med standardiserad prioriteringsordning för räknesätt och beräknar summan av alla värden. För vårt exempel får vi

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

Beräkna summan ovan modulo $10^9 + 7$.

Indata

Den första raden i indatan innehåller ett heltal $n$ ($1 \le n \le 10^6$), som anger strängens längd.

Den andra raden innehåller en sträng av längd $n$ som består av siffrorna 1–9.

Utdata

Skriv ut ett heltal, summan av alla uttryck modulo $10^9 + 7$.

Exempel

Indata

3
231

Utdata

397