两个正整数互质当且仅当它们的公约数不大于 1。
有些熊不想告诉 Radewoosh 如何解决某些算法问题。因此,拉德伍什将带着解决方案闯入那只熊的保险箱。要通过这扇门,他必须输入数字 1 到 n 的排列。当且仅当输入的排列 p1, p2, ..., pn 满足:
$$\forall_{1 \leq i < j \leq n} \text{coprime}(i,j) \Leftrightarrow \text{coprime}(p_i,p_j)$$
换句话说,两个不同的元素是互质的当且仅当它们的索引是互质的。
排列的某些元素可能已经固定。 Radewoosh 可以通过多少种方式填补剩余的空白,从而打开大门?打印以 109 + 7 为模的答案。
输入
输入的第一行包含一个整数 n (2 ≤ n ≤ 1 000 000)。
第二行包含 n 个整数 p1, p2, ..., pn (0 ≤ pi ≤ n),其中 pi = 0 表示要填充的间隙,pi ≥ 1 表示固定数字。
保证如果 i ≠ j 且 pi, pj ≥ 1,则 pi ≠ pj。
输出
打印以 109 + 7 为模(即模 1000000007)来填充间隙的方法数。
示例
输入 #1
4 0 0 0 0
输出 #1
4
输入 #2
5 0 0 1 2 0
输出 #2
2
输入 #3
6 0 0 1 2 0 0
输出 #3
0
输入#4
5 5 3 4 2 1
输出#4
0
注意
在第一个样本测试中,四个元素均未固定。满足给定条件的排列有四种:(1,2,3,4)、(1,4,3,2)、(3,2,1,4)、(3,4,1,2)。
在第二个样本测试中,必须有p3 = 1和p4 = 2。满足条件的两个排列是:(3,4,1,2,5),(5,4,1,2,3)。