#212. 1211. [HNOI2004]树的计数

1211. [HNOI2004]树的计数

#1211. [HNOI2004]树的计数

题目描述

一个有n个结点的树,设它的结点分别为v1, v2, …, vn,已知第i个结点vi的度数为di,问满足这样的条件的不同的树有多少棵。给定n,d1, d2, …, dn,编程需要输出满足d(vi)=di的树的个数。

输入格式

第一行是一个正整数n,表示树有n个结点。第二行有n个数,第i个数表示di,即树的第i个结点的度数。其中1<=n<=150,输入数据保证满足条件的树不超过10^17个。

输出格式

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

样例

样例输入

4                       

2 1 2 1  

样例输出

2

数据范围与提示