我哋有一個由 $n$ 個非零數碼組成嘅字串。我哋可以喺任意兩個相鄰數碼之間插入至多一個字符 $+$（加號）或者 $\cdot$（乘號）嚟生成一個表達式。例如，由字串 231 我哋可以生成九個表達式：

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

我哋按照標準嘅運算順序計算呢啲表達式嘅值，並求出所有結果嘅總和。對於上面嘅例子，我哋得到

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

請計算上述總和對 $10^9 + 7$ 取模嘅結果。

輸入格式

輸入嘅第一行包含一個整數 $n$（$1 \le n \le 10^6$），代表字串嘅長度。

第二行包含一個長度為 $n$ 且由數碼 1–9 組成嘅字串。

輸出格式

輸出一個整數，代表所有表達式之和對 $10^9 + 7$ 取模嘅結果。

範例

輸入

3
231

輸出

397