自从明明学了树结构，他对奇形怪状的树产生了浓厚的兴趣。在画了一棵又一棵各种各样的树后，他想到了一个问题：给定 $n$ 个标号为 $1$ 到 $n$ 的点，并允许在两点之间任意连线，要求最终连成一棵含 $n$ 个点的树，总共能画出多少棵不同的树呢？在着手解决这个问题的时候，他又想到另一个更一般的问题：给定 $n$ 个标号为 $1$ 到 $n$ 的点以及某些点最终的度数，并允许在两点之间任意连线，要求最终连成一棵含 $n$ 个点的树且树中各点的度满足上述要求，总共能画出多少棵不同的树呢？

明明思考了很久，也只会手算一些简单的情况，由于初学程序设计，他不知道如何写个程序来帮他解决这个问题。所以求助于准备参加 NOI2008 的你，请你帮他解决这个问题。

输入格式

第一行包含一个整数 $n$，表示树中的结点数，接下来的 $n$ 行依次表示结点 $1$ 到结点 $n$ 最终应该具有的度数，第 $i+1$ 行表示结点 $i$ 最终应该具有的度数 $D_i$，若第 $i$ 行为 $-1$，则表示对结点 $i$ 的度数没有要求。输入数据保证 $0 < n\le 1000$，$-1\le D_i < n $。

输出格式

仅包含一个整数，表示可以画出多少棵不同的树，若无解则输出 $0$。

样例数据

样例 1 输入

3
1
-1
-1

样例 1 输出

2