Við höfum streng sem samanstendur af $n$ tölustöfum sem eru ekki núll. Við getum búið til segð með því að skjóta inn í mesta lagi einu af táknunum $+$ (plús) eða $\cdot$ (margföldun) á milli hvaða tveggja samliggjandi tölustafa sem er. Til dæmis getum við búið til níu segðir úr strengnum 231:

$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ð reiknum gildi þessara segða samkvæmt hefðbundinni reikniröð aðgerða og finnum summu allra gildanna. Fyrir dæmið okkar fáum við

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

Reiknið summuna hér að ofan módulo $10^9 + 7$.

Inntak

Fyrsta lína inntaksins inniheldur eina heiltölu $n$ ($1 \le n \le 10^6$), sem táknar lengd strengsins.

Önnur línan inniheldur streng af lengd $n$ sem samanstendur af tölustöfunum 1–9.

Úttak

Skrifið út eina heiltölu, summu allra segða módulo $10^9 + 7$.

Dæmi

Inntak

3
231

Úttak

397