Nous avons une chaîne composée de $n$ chiffres non nuls. Nous pouvons produire une expression en insérant au plus un des caractères $+$ (plus) ou $\cdot$ (multiplier) entre deux chiffres consécutifs quelconques. Par exemple, à partir de la chaîne 231, nous pouvons produire neuf expressions :

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

Nous évaluons ces expressions selon l'ordre standard des opérations et calculons la somme de toutes les valeurs. Pour notre exemple, nous obtenons

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

Calculez la somme ci-dessus modulo $10^9 + 7$.

Entrée

La première ligne de l'entrée contient un entier $n$ ($1 \le n \le 10^6$), désignant la longueur de la chaîne.

La deuxième ligne contient une chaîne de longueur $n$ composée des chiffres 1–9.

Sortie

Affichez un entier, la somme de toutes les expressions modulo $10^9 + 7$.

Exemple

Entrée

3
231

Sortie

397