该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

样例下载

前置知识

Prüfer 数列是一种用于表示带标号无根树的序列，由德国数学家 Heinz Prüfer 于 1918 年在证明凯莱定理时首次提出。该数列通过删除特定顶点生成，长度为顶点数减 2，可实现树结构与整数序列间的双向转换。

Prüfer 序列是这样建立的：每次选择一个编号最小的叶结点并删掉它，然后在 Prüfer 序列中记录下它连接到的那个结点．重复 n-2 次后就只剩下两个结点，算法结束。

使用 Prüfer 序列重构原树时依次连接序列元素与未出现的最小标号节点，最后连接剩余两顶点即可还原完整树结构。

该方法最初用于组合数学中的树结构编码问题，其核心价值在于实现带标号无根树与 Prüfer 数列之间的一一对应关系，为图论研究提供标准化工具。

例如，下图是一棵 7 个结点的树的 Prüfer 序列构建过程：

最终的 Prüfer 序列就是 2, 2, 3, 3, 2.

题目描述

小明曾经见过一棵树。

他已经忘记了这棵树的形态。

但是他清楚地记得这是一棵无根无序树，包含 n 个结点，编号为 1 ~ n。

他还记得若干个结点的度。所谓结点的度，是指以该结点作为端点的树边的数量。

现在，他想把这棵树画出来。

问：根据小明的记忆，他能画出多少棵不同的树？

注：两棵树不同，当且仅当存在一条边连接的无序顶点对不同。

输入

第一行：一个整数 N；

接下来 N 行，每行一个整数 $d_i$，表示编号为 i 结点的度（若 $d_i=-1$ 则表示他忘记了结点 i 的度）。

输出

一个整数，表示答案。

样例输入

4
1
2
1
-1

样例输出

2

样例解释

1-2-4-3

1-4-2-3

数据范围

0 < N ≤ 1000