Một cầu thang có ~ n ~ bậc thang được đánh số từ 1 đến ~ n ~, trong đó có một số bậc bị hỏng không thể bước vào. Một người đứng ở bậc thứ 0 (ở nền nhà) muốn lên đến bậc thứ ~ n ~ mà chỉ có thể bước với số bước là 1 bậc hoặc 2 bậc. Yêu cầu: Hãy cho biết có bao nhiêu cách đi từ bậc 0 đến bậc thứ ~ n ~.

Dữ liệu vào

• Dòng đầu là số nguyên dương ~ n ~ ~ (n ≤ 5000) ~.
• Dòng thứ hai là ~ n ~ số 0 hoặc 1 biểu thị tương ứng 1 là bậc tốt, 0 là bậc bị hỏng; giữa hai số cách nhau ít nhất 1 dấu cách

Kết quả

• Một số nguyên duy nhất cho biết kết quả tìm được.

Ràng buộc

Ví dụ:

Input 1

4
1 1 0 1 

Output 1

2