#1211. [HNOI2004]树的计数

[HNOI2004]树的计数

题目描述

一个有 nn 个结点的树,设它的结点分别为 v1,v2,,vnv_1,v_2,…,v_n,已知第 ii 个结点 viv_i 的度数为 did_i,给定 n,d1,d2,...,dnn,d_1,d_2,...,d_n,问满足这样的条件的不同的树有多少棵。

输入格式

第一行是一个正整数 nn ,表示树有 nn 个结点。

第二行有 nn 个数,第 ii 个数表示 did_i,即树的第 ii 个结点的度数。

输出格式

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

样例输入

4
2 1 2 1

样例输出

2

数据规模与约定

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

题目来源

HNOI 2004\texttt{HNOI 2004}