我們有一個由 $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