Description

Consider a tree with $n$ nodes, denoted $v_1, v_2, \ldots, v_n$. The degree of node $v_i$ is given as $d_i$. How many distinct trees satisfy these conditions?

Input Format

The first line contains a positive integer $n$, the number of nodes in the tree. The second line contains $n$ integers; the $i$-th of them is $d_i$, the degree of node $v_i$.

Output Format

Output the number of trees that satisfy the conditions.

4                     
2 1 2 1

2

Hint

Constraints: $1 \le n \le 150$. It is guaranteed that the number of valid trees does not exceed $10^{17}$.

Translated by ChatGPT 5