Лунтик вышел на утреннюю прогулку и нашел массив \(a\) длины \(n\). Он посчитал сумму \(s\) элементов массива (\(s= \sum_{i=1}^{n} a_i\)). Лунтик называет подпоследовательность массива \(a\) почти полной, если сумма чисел в этой подпоследовательности равна \(s-1\).
Лунтик очень хочет узнать количество почти полных подпоследовательностей массива \(a\). Но ему надо возвращаться домой, поэтому он просит вас решить эту задачу!
Напоминаем, что последовательность \(x\) является подпоследовательностью \(y\), если \(x\) может быть получена из \(y\) удалением нескольких (возможно, ни одного или всех) элементов.
Выходные данные
Для каждого набора входных данных выведите количество почти полных подпоследовательностей массива.
Примечание
В первом наборе входных данных \(s=1+2+3+4+5=15\), из всех подпоследовательностей почти полной будет только \((2,3,4,5)\), сумма в ней равна \(2+3+4+5=14=15-1\).
Во втором наборе входных данных нет почти полных подпоследовательностей.
В третьем наборе входных данных \(s=1+0=1\), почти полными будут подпоследовательности \((0)\) и \(()\) (пустая подпоследовательность имеет сумму \(0\)).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
5
1 2 3 4 5
2
1000 1000
2
1 0
5
3 0 2 1 1
5
2 1 0 3 0
|
1
0
2
4
4
|