[HNOI2004]树的计数

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

给定 $n$ 以及 $d_1, d_2, \dots, d_n$，请输出满足 $d(v_i)=d_i$ 的树的个数。

输入格式

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

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

输出格式

一行一个整数，表示满足条件的树有多少棵。

样例输入

4
2 1 2 1

样例输出

2

样例解释

度数序列为 $2, 1, 2, 1$，说明 $v_1$ 与 $v_3$ 是链的中间两点，$v_2$ 与 $v_4$ 是链的两个端点。满足条件的树共 $2$ 棵：

$$v_2-v_1-v_3-v_4\qquad\text{和}\qquad v_4-v_1-v_3-v_2.$$

数据范围

• $1\le n\le 150$；
• 输入数据保证满足条件的树不超过 $10^{17}$ 棵。

来源与许可

本题为 HNOI 2004 试题「树的计数」，题面与测试数据整理自 BZOJ 1211。

样例 1

输入

4
2 1 2 1

输出

2