Mamy napis składający się z $n$ niezerowych cyfr. Możemy utworzyć wyrażenie, wstawiając co najwyżej jeden ze znaków $+$ (plus) lub $\cdot$ (mnożenie) pomiędzy dowolne dwie kolejne cyfry. Na przykład z napisu 231 możemy utworzyć dziewięć wyrażeń:

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

Obliczamy wartości tych wyrażeń zgodnie ze standardową kolejnością wykonywania działań i wyznaczamy sumę wszystkich wartości. Dla naszego przykładu otrzymujemy

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

Oblicz powyższą sumę modulo $10^9 + 7$.

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą $n$ ($1 \le n \le 10^6$), oznaczającą długość napisu.

Drugi wiersz zawiera napis o długości $n$ składający się z cyfr 1–9.

Wyjście

Wypisz jedną liczbę całkowitą — sumę wszystkich wyrażeń modulo $10^9 + 7$.

Przykład

Wejście

3
231

Wyjście

397