Задача STEPS. 

В комп'ютерній грі "Страшна помста 2" головному герою -безстрашному лицарю - потрібно спуститися по хиткій драбині, що має N сходинок, до темного підземелля. Герой може спуститися, ступаючи на кожну сходинку, перескакувати через одну або дві сходинки. Але злі чаклуни підпиляли деякі сходинки, тому на них ставати небезпечно. Скількома різними способами лицар може потрапити з першої сходинки на N-у?
Ви повинні написати програму STEPS, яка читає вхідні дані з клавіатури  та виводить відповідь на екран
Формат введення:
N
c[1]
c[2]
...
c[N]

Формат виведення:
X

Тут N - кількість сходинок, c[k]=1, якщо k-та сходинка неушкоджена, та c[k]=0, якщо k-а сходинка підпиляна.
Обмеження:
1<N<40;
c[1]=1; c[N]=1;
вхідні дані такі, що герой завжди може потрапити з першої на N-у сходинку хоча б одним способом.
Приклад:
Введення:
6
1
0
1
1
0
1
Виведення:
3

В цьому прикладі драбина складається з 6-и сходинок, причому друга та п'ята сходинка підпиляні. 
Потрапити з 1-ї сходинки на 6-у можливо 3-ма способами. Перший спосіб: стрибок через одну сходинку, крок на наступну та стрибок через сходинку. Другий спосіб: стрибок через сходинку та стрибок через 2 сходинки. Третій спосіб: стрибок через 2 сходинки і стрибок через 1 сходинку.