Вася обожает всё сладкое. Его любимый шоколад является палочкой, состоящей из кусочков, каждый из которых может содержать орешек. Вася хочет разломать шоколад на несколько частей так, чтобы любая часть содержала ровно один орешек, и любой разлом проходил между двумя соседними кусочками.
Посчитайте количество способов, которыми Вася может это сделать. Два способа считаются различными, если в одном из них присутствует разлом в конкретной позиции, который отсутствует в другом способе.
Обратите внимание, что если не сделать ни одного разлома, то вся шоколадка будет представлять собой один кусочек. В этом случае, в этом кусочке также должен быть ровно один орешек.
Выходные данные
Выведите количество способов разломать шоколад на несколько частей так, чтобы в каждой из них находился ровно один орешек.
Примечание
В первом примере есть ровно один орешек, поэтому количество способов равно 1 — не делать ни одного разлома.
Во втором примере можно разломать шоколад четырьмя способами:
10|10|1
1|010|1
10|1|01
1|01|01
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
0 1 0
|
1
|
|
2
|
5
1 0 1 0 1
|
4
|