Вам дано $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$.