Coprime Permutation

2000ms

262144K

Description:

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₁, p₂, ..., p_n satisfies:

$\text{[math]}$

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 10⁹ + 7.

Input:

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

The second line contains n integers p₁, p₂, ..., 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.

Output:

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

Sample Input:

4
0 0 0 0

Sample Output:

Sample Input:

5
0 0 1 2 0

Sample Output:

Sample Input:

6
0 0 1 2 0 0

Sample Output:

Sample Input:

5
5 3 4 2 1

Sample Output:

Note:

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₃ = 1 and p₄ = 2. The two permutations satisfying the conditions are: (3,4,1,2,5), (5,4,1,2,3).

Informação

Provedor Codeforces

Código CF698F