Вам дано n чисел a1,a2,…,an, кожне з яких 0 або 1. Вам потрібно порахувати кількість десяткових чисел, які складаються з n+1 цифр і задовольняють такій умові: якщо, позначити bi як i-у цифру числа, то bi<bi+1, якщо ai=1, а також bi>bi+1 якщо ai=0 для i від 1 до n.
Так як відповідь може бути досить великою, виведіть її по модулю 109+7.
Перший рядок містить одне ціле число n (1≤n≤105).
Другий рядок містить n цілих чисел a1,a2,…,an (0≤ai≤1).
Виведіть одне ціле число — кількість таких чисел по модулю 109+7.
Числа, які задовольняють умові в першому прикладі: 10,20,21,30,31,32,…,96,97,98. Їх всього 1+2+3+⋯+8+9=45.