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