← 返回题目列表

Codeforces · 698/F

F. 互质排列

中文机器翻译题面 查看原题

两个正整数互质当且仅当它们的公约数不大于 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)。