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