Умова задачі
JOI-кун навчається в $1$-му класі початкової школи. JOI-куну дуже подобаються додавання та віднімання, які він щойно вивчив, тому, бачачи ряд цифр, він грається, вставляючи знак = між останніми $2$ цифрами, а між рештою сусідніх цифр обов'язково вставляючи + або -, щоб утворилася рівність. Наприклад, із 8 3 2 4 8 7 2 4 0 8 8 можна скласти рівність 8+3-2-4+8-7-2-4-0+8=8.
Склавши рівність, JOI-кун обчислює її, щоб перевірити, чи є вона правильною. Проте JOI-кун ще не знає від'ємних чисел і не вміє виконувати обчислення з числами, що перевищують $20$. Тому серед правильних рівностей JOI-кун може перевірити лише ті, у яких під час обчислення лівої частини зліва направо всі проміжні результати не менші за $0$ і не більші за $20$. Наприклад, 8+3-2-4-8-7+2+4+0+8=8 — правильна рівність, але оскільки значення 8+3-2-4-8, що виникає під час обчислень, є від'ємним, JOI-кун не може перевірити, чи правильна ця рівність.
За заданою у вхідних даних послідовністю цифр напишіть програму, яка знаходить кількість правильних рівностей, які JOI-кун може скласти та перевірити.
Вхідні дані
Вхідний файл складається з $2$ рядків. У $1$-му рядку записано ціле число $N$ ($3 \le N \le 100$), що означає кількість записаних підряд цифр. У $2$-му рядку через пробіл записано $N$ цілих чисел від $0$ до $9$ включно.
У $60\%$ вхідних даних кількість правильних рівностей, які JOI-кун може скласти та перевірити, не перевищує $2^{31}-1$. Крім того, в усіх вхідних даних кількість правильних рівностей, які JOI-кун може скласти та перевірити, не перевищує $2^{63}-1$.
Вихідні дані
Виведіть в $1$ рядку ціле число — кількість правильних рівностей, які JOI-кун може скласти та перевірити.
Приклади вводу та виводу
Приклад вводу 1
11 8 3 2 4 8 7 2 4 0 8 8
Приклад виводу 1
10
Приклад вводу 2
40 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1
Приклад виводу 2
7069052760
У прикладі вводу $1$ JOI-кун може скласти та перевірити такі $10$ правильних рівностей:
8+3-2-4+8-7-2-4-0+8=88+3-2-4+8-7-2-4+0+8=88+3+2+4-8-7+2-4-0+8=88+3+2+4-8-7+2-4+0+8=88+3+2-4+8-7+2+4-0-8=88+3+2-4+8-7+2+4+0-8=88-3+2+4-8+7+2+4-0-8=88-3+2+4-8+7+2+4+0-8=88-3+2-4+8+7+2-4-0-8=88-3+2-4+8+7+2-4+0-8=8
Тому слід вивести $10$.
Зверніть увагу, що в прикладі вводу $2$ відповідь не вміщується в діапазон $32$-бітного знакового цілого числа.
(Додано $21$.$2$.$2015$) За зауваженням користувача було виявлено, що серед рівностей у поясненні до прикладу вводу $1$ була помилка. Наразі її виправлено. $5$-та рівність мала вигляд 8+3-2-4+8-7+2+4-0-8=8, її було виправлено на 8+3+2-4+8-7+2+4-0-8=8. Також $6$-та рівність мала вигляд 8+3-2-4+8-7+2+4+0-8=8, її було виправлено на 8+3+2-4+8-7+2+4+0-8=8.