Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

F. Coprime Permutation

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputTwo 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 10^{9} + 7.

Input

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}.

Output

Print the number of ways to fill the gaps modulo 10^{9} + 7 (i.e. modulo 1000000007).

Examples

Input

4

0 0 0 0

Output

4

Input

5

0 0 1 2 0

Output

2

Input

6

0 0 1 2 0 0

Output

0

Input

5

5 3 4 2 1

Output

0

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

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/27/2017 03:38:11 (c4).

Desktop version, switch to mobile version.
User lists

Name |
---|