Iahub 对发明冒泡排序图感到非常高兴,以至于他整天呆在办公室里编写排列。 Iahubina 很生气,因为她对 Iahub 来说不再重要了。当 Iahub 离开时,Iahubina 来到他的办公室并破坏他的研究工作。
女孩发现了研究的重要排列。该排列包含 n 个不同的整数 a1, a2, ..., an (1 ≤ ai ≤ n)。作为报复,她用 -1 值替换了一些排列元素。
当 Iahub 发现他的重要排列被破坏时,他尝试恢复它。关于排列,他唯一记得的是它没有任何固定点。排列的不动点是元素 ak ,其值等于 k (ak = k)。你的工作是向 Iahub 证明尝试恢复它不是一个好主意。输出排列数,该排列数最初可能是 Iahub 的重要排列,模 1000000007 (109 + 7)。
输入
第一行包含整数 n (2 ≤ n ≤ 2000)。第二行有n个整数,代表Iahubina将部分值替换为-1后Iahub的重要排列。
保证给定排列中没有不动点。此外,给定序列至少包含两个数字-1,并且每个正数在序列中最多出现一次。保证至少有一种合适的排列。
输出
输出一个整数,Iahub 可以恢复其排列的方式数,模 1000000007 (109 + 7)。
示例
输入 #1
5 -1 -1 4 3 -1
输出 #1
2
注意
对于第一个测试示例,有两个没有固定点的排列:[2, 5, 4, 3, 1] 和 [5, 1, 4, 3, 2]。任何其他排列都至少有一个固定点。