Впорядковані цифри

Вам дано $n$ чисел $a_1,a_2,\dots ,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$.

Input

Перший рядок містить одне ціле число $n$ ($1\le n\le 10^5$).

Другий рядок містить $n$ цілих чисел $a_1,a_2,\dots ,a_n$ ($0\le a_i\le 1$).

Output

Виведіть одне ціле число — кількість таких чисел по модулю $10^9+7$.

Examples

Note

Числа, які задовольняють умові в першому прикладі: $10,20,21,30,31,32,\dots ,96,97,98$. Їх всього $1+2+3+\cdots +8+9=45$.