题目描述

今天是个阳光明媚的日子，体育老师打算在这一天进行本学期的体育测试。

班上共有 $n$ 个人，学号从 $1$ 到 $n$ 排列。

我们不妨假设测试项目只有一项，按照体育老师的原定计划，只需要所有人按照学号顺序依次进行测试即可。

但是当天学校要组织集体注射新冠疫苗，每名同学都预约了特定的时间注射，因此可能会有时间上的冲突。

于是老师不得不重新调整每个人的考核顺序。具体来说，他会选择一个大小为 $n$ 的排列 $p$，让同学们按照学号 $p_1\sim p_n$ 的顺序依次进行测试。

对于每个人来说，注射疫苗的时间冲突使他要么不得不早走，要么不得不晚到。

每个人有一个时间要求 $a_i$，其中 $a_i>0$ 表示他需要早走，必须不晚于第 $a_i$ 个进行测试；$a_i<0$ 表示他需要晚到，必须不早于第 $|a_i|$ 个进行测试。

你需要帮忙算出：符合要求的排列 $p$ 一共有多少个？

输入格式

第一行是一个正整数 $n$。

第二行有 $n$ 个整数 $a_i$。

输出格式

一个非负整数表示答案对 $10^9 + 7$ 取模的结果。

样例

4
2 -2 -3 4

6

如下 $6$ 个排列符合要求：

1 2 3 4
1 2 4 3
1 4 2 3
1 4 3 2
4 1 2 3
4 1 3 2

附加文件中还有一组样例 test2.in 与 test2.out。

数据范围及约定

对于全部的数据，$1\le n\le 5\times 10^3$，$1\le |a_i|\le n$。