Решение задачи Шоколад с Codeforces

Вася обожает всё сладкое. Его любимый шоколад является палочкой, состоящей из кусочков, каждый из которых может содержать орешек. Вася хочет разломать шоколад на несколько частей так, чтобы любая часть содержала ровно один орешек, и любой разлом проходил между двумя соседними кусочками.

Посчитайте количество способов, которыми Вася может это сделать. Два способа считаются различными, если в одном из них присутствует разлом в конкретной позиции, который отсутствует в другом способе.

Обратите внимание, что если не сделать ни одного разлома, то вся шоколадка будет представлять собой один кусочек. В этом случае, в этом кусочке также должен быть ровно один орешек.