Abbiamo una stringa composta da $n$ cifre diverse da zero. Possiamo produrre un'espressione inserendo al massimo uno dei caratteri $+$ (più) o $\cdot$ (moltiplicazione) tra due cifre consecutive qualsiasi. Ad esempio, dalla stringa 231 possiamo produrre nove espressioni:

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

Valutiamo queste espressioni secondo il normale ordine delle operazioni e calcoliamo la somma di tutti i valori. Per il nostro esempio otteniamo

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

Calcola la somma precedente modulo $10^9 + 7$.

Input

La prima riga dell'input contiene un intero $n$ ($1 \le n \le 10^6$), che indica la lunghezza della stringa.

La seconda riga contiene una stringa di lunghezza $n$ composta dalle cifre 1–9.

Output

Stampa un intero, la somma di tutte le espressioni modulo $10^9 + 7$.

Esempio

Input

3
231

Output

397