Время ломать лестницы
В марсианском городке Пелдано отмечали день лестниц. В завершение торжественной церемонии по традиции ломают ступени, ведущие в здание городского центра (не спрашивайте «зачем?» — таковы марсианские обычаи). При этом ломают только некоторые ступени, оставляя другие целыми.
Затем, по традиции, каждый житель города поднимается по этим поломанным ступеням, делая шаг либо на одну ступеньку вверх, либо перепрыгивая через одну. Марсиане не могут наступать на поломанные ступеньки. Путь начинается с первой ступеньки и заканчивается на последней.
Согласно священному обычаю, каждый житель должен пройти уникальный путь от нижней ступеньки до верхней — то есть ни один марсианин не может преодолеть лестницу тем же способом, что и кто-либо до него.По состоянию ступеней вам необходимо определить, сколько марсиан может преодолеть их уникальными путями.
Входные данные
В первой строке входных данных задается число N — количество ступенек в лестнице (2 ≤ N ≤ 1000), а затем следуют N чисел — 0 или 1. 0 означает, что соответствующая ступенька поломана, а 1 — что она целая.
Выходные данные
Выходные данные должны содержать одно целое число — количество марсиан, которые могли бы преодолеть лестницу при условии, что каждый из них движется уникальным путем.