题目描述

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

输入格式

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

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

输出格式

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

样例

4                     
2 1 2 1

2

数据范围

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