[HNOI2004]树的计数

题目描述

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

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

4                     
2 1 2 1

输出样例 #1

2

说明

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