You have to tell the number of valid permutations from 1 to N which follow the rules array. Rules array is an array of size N-1 where the value of ith element tell about the relative position of numbers i and i+1 with respect to each other. The elements of rules array can be either 1 or 0. If it is 1, then in a valid permutation, the number i will come before the number i+1. If it is 0, then in a valid permutation, the number i can come either before or after the number i+1. There is no other restriction on the relative positions of numbers apart from rules array.

Print the number of valid permutations modulo 10^9+7 in a new line.

Input Format

First line contain a integer N denoting the number of elements in permutation. Next N-1 lines contains an integer each - the elements of the rules array.

Output Format

Print the answer in a new line.

Constraints

2<= N<= 5*10^5
0<= ith element of rules array<= 1