题目描述

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

输入格式

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

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

输出格式

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

样例输入

4
2 1 2 1

样例输出

2

数据规模与约定

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

题目来源

$\texttt{HNOI 2004}$