CF698F.Coprime Permutation

Two positive integers are coprime if and only if they don't have a common divisor greater than 1.

Some bear doesn't want to tell Radewoosh how to solve some algorithmic problem. So, Radewoosh is going to break into that bear's safe with solutions. To pass through the door, he must enter a permutation of numbers 1 through n. The door opens if and only if an entered permutation _p_1, _p_2, ..., p__n satisfies:

In other words, two different elements are coprime if and only if their indices are coprime.

Some elements of a permutation may be already fixed. In how many ways can Radewoosh fill the remaining gaps so that the door will open? Print the answer modulo 109 + 7.

两个正整数互质，当且仅当它们没有大于 1 的公共因数。

某只熊不愿告诉 Radewoosh 如何解决某个算法问题。因此，Radewoosh 打算潜入这只熊存放解法的保险箱。要通过门前的通道，他必须输入一个 $1$ 到 $n$ 的排列。当且仅当所输入的排列 $p_1,\,p_2,\,...,\,p_n$ 满足以下条件时，门才会打开：

换言之，排列中两个不同元素互质，当且仅当它们的下标互质。

该排列中部分位置的元素可能已被预先固定。Radewoosh 有多少种方式填满剩余空位，使得门能够打开？请输出答案对 $10^9 + 7$ 取模的结果。

The first line of the input contains one integer n (2 ≤ n ≤ 1 000 000).

The second line contains n integers _p_1, _p_2, ..., p__n (0 ≤ p__i ≤ n) where p__i = 0 means a gap to fill, and p__i ≥ 1 means a fixed number.

It's guaranteed that if i ≠ j and p__i, p__j ≥ 1 then p__i ≠ p__j.

输入的第一行包含一个整数 $n$（$2 \leq n \leq 1\,000\,000$）。

第二行包含 $n$ 个整数 $p_1,\,p_2,\,\dots,\,p_n$（$0 \leq p_i \leq n$），其中 $p_i = 0$ 表示待填充的空位，而 $p_i \geq 1$ 表示一个固定的数字。

保证：若 $i \neq j$ 且 $p_i,\,p_j \geq 1$，则 $p_i \neq p_j$。

Print the number of ways to fill the gaps modulo 109 + 7 (i.e. modulo 1000000007).

输出填满空隙的方案数对 $10^9 + 7$（即对 $1000000007$ 取模）的结果。

In the first sample test, none of four element is fixed. There are four permutations satisfying the given conditions: (1,2,3,4), (1,4,3,2), (3,2,1,4), (3,4,1,2).

In the second sample test, there must be _p_3 = 1 and _p_4 = 2. The two permutations satisfying the conditions are: (3,4,1,2,5), (5,4,1,2,3).

在第一个样例测试中，四个元素均未被固定。共有四种满足给定条件的排列：$(1,2,3,4)$、$(1,4,3,2)$、$(3,2,1,4)$、$(3,4,1,2)$。

在第二个样例测试中，必须有 $p_3 = 1$ 且 $p_4 = 2$。满足条件的两种排列为：$(3,4,1,2,5)$、$(5,4,1,2,3)$。