Time to break the stairs
In the Martian town of Peldano, a unique event known as the "Day of Stairs" is celebrated. At the conclusion of this ceremony, it is customary to break some of the steps leading to the city center building. This peculiar tradition dictates that only certain steps are broken, while others remain intact.
During this event, each resident of Peldano must ascend the stairs, choosing to either step up one step or skip a step. Importantly, Martians are not allowed to step on broken steps. The journey begins at the first step and concludes at the last step.
According to the sacred tradition, every resident must follow a distinct path from the bottom to the top of the stairs, ensuring that no two Martians use the same route.
Your task is to determine how many Martians can ascend the stairs, each using a unique path, based on the current condition of the steps.
Input Data
The input begins with an integer N, representing the number of steps in the staircase (2 ≤ N ≤ 1000). This is followed by a sequence of N integers, each either 0 or 1. A 0 indicates that the step is broken, while a 1 indicates that the step is intact.
Output Data
The output should be a single integer, representing the number of Martians who can ascend the stairs, each taking a unique path.