We have a string consisting of $n$ non-zero digits. We can produce an expression by inserting at most one of the characters $+$ (plus) or $\cdot$ (multiply) between any two consecutive digits. For instance, from the string 231 we can produce nine 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$.

We evaluate these expressions with the standard order of operations, and calculate the sum of all values. For our example we get

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

Calculate the above sum modulo $10^9 + 7$.

Input

The first line of the input contains one integer $n$ ($1 \le n \le 10^6$), denoting the length of the string.

The second line contains a string of length $n$ consisting of digits 1–9.

Output

Output one integer, the sum of all expressions modulo $10^9 + 7$.

Example

Input

3
231

Output

397