There is a tree with $n$ nodes, denoted as $v_1, v_2, \dots, v_n$. Given the degree $d_i$ of each node $v_i$, determine the number of distinct trees that satisfy these conditions.

Given $n$ and $d_1, d_2, \dots, d_n$, write a program to output the number of trees such that the degree of $v_i$ is $d_i$.

Input

The first line of the input file contains a positive integer $n$, representing the number of nodes in the tree. The second line contains $n$ integers, where the $i$-th number represents $d_i$, the degree of the $i$-th node. It is guaranteed that $1 \le n \le 150$ and the number of such trees does not exceed $10^{17}$.

Output

Output the number of trees that satisfy the given conditions.

Examples

Input 1

4
2 1 2 1

Output 1

2