Wir haben eine Zeichenkette, die aus $n$ von null verschiedenen Ziffern besteht. Wir können einen Ausdruck erzeugen, indem wir zwischen je zwei aufeinanderfolgenden Ziffern höchstens eines der Zeichen $+$ (Plus) oder $\cdot$ (Mal) einfügen. Zum Beispiel können wir aus der Zeichenkette 231 neun Ausdrücke erzeugen:

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

Wir werten diese Ausdrücke nach der üblichen Punkt-vor-Strich-Regel aus und berechnen die Summe aller Werte. Für unser Beispiel erhalten wir

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

Berechne die obige Summe modulo $10^9 + 7$.

Eingabe

Die erste Zeile der Eingabe enthält eine ganze Zahl $n$ ($1 \le n \le 10^6$), die die Länge der Zeichenkette angibt.

Die zweite Zeile enthält eine Zeichenkette der Länge $n$, die aus den Ziffern 1–9 besteht.

Ausgabe

Gib eine ganze Zahl aus, die Summe aller Ausdrücke modulo $10^9 + 7$.

Beispiel

Eingabe

3
231

Ausgabe

397