树的计数

【题目描述】

一个有 $n$ 个结点的树，设它的结点分别为 $v_1, v_2, …, v_n$，已知第 $i$ 个结点 $v_i$ 的度数为 $d_i$，问满足这样的条件的不同的树有多少棵。

【输入格式】

输入文件第一行是一个正整数 $n$，表示树有 $n$ 个结点。

第二行有 $n$ 个数，第 $i$ 个数 $di$ 表示树的第 $i$ 个结点的度数。

其中 $1 \leq n \leq 150$，输入数据保证满足条件的树不超过 $10^{18}$ 个。

【输出格式】

输出满足条件的树有多少棵。

【样例输入】

4
2 1 2 1

【样例输出】

【数据规模】

非官方数据，数据较弱

对于 $60\%$ 的数据，$n \leq 5$;

对于 $100\%$ 的数据，$n \leq 30$;