树的计数

• 时间限制：1 秒
• 内存限制：512 MiB
• 输入：标准输入
• 输出：标准输出

题目描述

有一棵包含 $n$ 个带编号节点的无根树，节点编号为 $1,2,\ldots,n$。给定每个节点的度数 $d_i$，求满足这些度数的不同标号树数量。

若不存在满足条件的树，输出 $0$。

输入格式

第一行一个正整数 $n$，表示节点数。

第二行 $n$ 个整数 $d_1,d_2,\ldots,d_n$，表示各节点的度数。

输出格式

输出一个非负整数，表示满足条件的标号树数量。

样例输入

4
2 1 2 1

样例输出

2

数据范围

对于所有数据，$1\le n\le150$，$0\le d_i\le n-1$，并保证答案不超过 $10^{17}$。