[HNOI2004] 树的计数

题目描述

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

输入格式

输入文件第一行是一个正整数 $n$ ，表示树有 $n$ 个结点。第二行有 $n$ 个数，第 $i$ 个数表示 $d_i$，即树的第 $i$ 个结点的度数。

输出格式

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

样例 #1

样例输入 #1

4                     
2 1 2 1

样例输出 #1

2

提示

$1\le n\le 150$，保证满足条件的树不超过 $10^{17}$ 个。