eolymp
bolt
Try our new interface for solving problems
Məsələlər

Час ламати сходи

Час ламати сходи

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

У марсіанському містечку Пелдано відбувався день східців. Наприкінці урочистої церемонії традиційно ламають сходи, які ведуть у будівлю міського центру (не задавайтеся питанням «навіщо?» - такі вже марсіанські традиції). При цьому ламають тільки деякі сходи, залишаючи інші цілими.

Далі за традицією кожен із жителів міста підіймається цими поламаними сходами ступаючи за один крок або на одну сходинку вгору, або перестрибуючи через одну. Марсіани не можуть ставати на поламані сходинки. Рух починається на першій сходинці і закінчується на останній.

Як наказує святий звичай, кожен із жителів має проробити унікальний шлях від нижньої сходинки до верхньої – тобто жоден марсіанин не може подолати сходи у той же спосіб, як це зробив хто-небудь до нього.За станом сходів вам необхідно визначити, скільки марсіан може подолати їх унікальними шляхами.

Giriş verilənləri

У вхідних даних спочатку задається число N – кількість сходинок у сходах (2 ≤ N ≤ 1000), а далі N чисел – 0 або 1. 0 означає, що відповідна сходинка поламана, а 1 – що вона ціла.

Çıxış verilənləri

Вихідний рядок повинен містити єдине ціле число – кількість марсіан, які могли б подолати сходи за умови, що кожен з них рухається унікальним шляхом.

Nümunə

Giriş verilənləri #1
4 1 1 1 1
Çıxış verilənləri #1
3
Giriş verilənləri #2
3 1 0 1
Çıxış verilənləri #2
1
Giriş verilənləri #3
3 1 0 0
Çıxış verilənləri #3
0