Vi har en streng som består av $n$ sifre ulik null. Vi kan lage et uttrykk ved å sette inn høyst ett av tegnene $+$ (pluss) eller $\cdot$ (gange) mellom hvilke som helst to påfølgende sifre. For eksempel kan vi fra strengen 231 lage ni uttrykk:

$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 evaluerer disse uttrykkene med standard regnerekkefølge, og beregner summen av alle verdiene. For eksempelet vårt får vi

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

Beregn summen ovenfor modulo $10^9 + 7$.

Inndata

Den første linjen i inndataene inneholder ett heltall $n$ ($1 \le n \le 10^6$), som angir lengden på strengen.

Den andre linjen inneholder en streng med lengde $n$ bestående av sifrene 1–9.

Utdata

Skriv ut ett heltall, summen av alle uttrykkene modulo $10^9 + 7$.

Eksempel

Inndata

3
231

Utdata

397