我们有一个由 $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$ 的结果。

样例

输入样例 1

3
231

输出样例 1

397