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

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

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

Вхідні дані

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

Вихідні дані

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