Counting Constrained Consecutive Arrays

Given an integer N, consider an array nums of length N which is a permutation of the numbers from 1 to N (i.e. all elements are distinct). For every index i with 1 ≤ i ≤ N-1, there is a relationship between nums[i] and nums[i+1] that is one of the following:

• Continuous: nums[i+1] = nums[i] + 1
• Noncontinuous: nums[i+1] ≠ nums[i] + 1

You are given the relationship for every adjacent pair in the array. Your task is to count the number of valid arrays nums which satisfy these conditions.

Note: If N = 1, then there is only one array.

inputFormat

The input consists of two lines:

1. The first line contains an integer N (1 ≤ N).
2. The second line contains N-1 space‐separated integers. Each integer is either 1 or 0. A value of 1 indicates that the two adjacent numbers are in a continuous relationship (i.e. the next number must equal the previous number plus one), while a value of 0 indicates a noncontinuous relationship.

outputFormat

Output a single integer — the number of valid arrays that satisfy the given conditions.

sample

1

1