Tenemos una cadena que consta de $n$ dígitos distintos de cero. Podemos producir una expresión insertando a lo sumo uno de los caracteres $+$ (más) o $\cdot$ (multiplicar) entre cualesquiera dos dígitos consecutivos. Por ejemplo, a partir de la cadena 231 podemos producir nueve expresiones:

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

Evaluamos estas expresiones con el orden estándar de operaciones y calculamos la suma de todos los valores. Para nuestro ejemplo obtenemos

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

Calcula la suma anterior módulo $10^9 + 7$.

Entrada

La primera línea de la entrada contiene un entero $n$ ($1 \le n \le 10^6$), que denota la longitud de la cadena.

La segunda línea contiene una cadena de longitud $n$ formada por los dígitos 1–9.

Salida

Imprime un entero, la suma de todas las expresiones módulo $10^9 + 7$.

Ejemplo

Entrada

3
231

Salida

397