Codeforces Round 340 (Div. 2) |
---|
Закончено |
Вася обожает всё сладкое. Его любимый шоколад является палочкой, состоящей из кусочков, каждый из которых может содержать орешек. Вася хочет разломать шоколад на несколько частей так, чтобы любая часть содержала ровно один орешек, и любой разлом проходил между двумя соседними кусочками.
Посчитайте количество способов, которыми Вася может это сделать. Два способа считаются различными, если в одном из них присутствует разлом в конкретной позиции, который отсутствует в другом способе.
Обратите внимание, что если не сделать ни одного разлома, то вся шоколадка будет представлять собой один кусочек. В этом случае, в этом кусочке также должен быть ровно один орешек.
В первой строке находится целое число n (1 ≤ n ≤ 100) — количество кусочков в шоколаде.
Во второй строке идут n целых чисел ai (0 ≤ ai ≤ 1), где 0 обозначает кусочек без орешка, а 1 — кусочек с орешком.
Выведите количество способов разломать шоколад на несколько частей так, чтобы в каждой из них находился ровно один орешек.
3
0 1 0
1
5
1 0 1 0 1
4
В первом примере есть ровно один орешек, поэтому количество способов равно 1 — не делать ни одного разлома.
Во втором примере можно разломать шоколад четырьмя способами:
10|10|1
1|010|1
10|1|01
1|01|01
Название |
---|