Задачи
Впорядковані цифри
Впорядковані цифри
Вам дано $n$ чисел $a_1, a_2, \ldots, a_n$, кожне з яких $0$ або $1$. Вам потрібно порахувати кількість десяткових чисел, які складаються з $n+1$ цифр і задовольняють такій умові: якщо, позначити $b_i$ як $i$-у цифру числа, то $b_i < b_{i+1}$, якщо $a_i=1$, а також $b_i > b_{i+1}$ якщо $a_i=0$ для $i$ від $1$ до $n$.
Так як відповідь може бути досить великою, виведіть її по модулю $10^9 + 7$.
\InputFile
Перший рядок містить одне ціле число $n$ ($1 \le n \le 10^5 $).
Другий рядок містить $n$ цілих чисел $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 1$).
\OutputFile
Виведіть одне ціле число~--- кількість таких чисел по модулю $10^9 + 7$.
\Note
Числа, які задовольняють умові в першому прикладі: $10, 20, 21, 30, 31, 32, \dots, 96, 97, 98$. Їх всього $1 + 2 + 3 + \dots + 8 + 9 = 45$.
Входные данные #1
1 0
Выходные данные #1
45
Входные данные #2
7 1 1 1 0 0 0 1
Выходные данные #2
58095