Условие задачи
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.