Дана строка, состоящая из $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