跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#F1157. Coprime Permutation

  • ID: 1163
  • 传统题
  • 2000ms
  • 256MiB
  • 尝试: 0
  • AC · 已通过: 0
  • 教学难度:挑战
  • 上传者:
  • 组合数学
  • 数论
  • 数学
  • 挑战
  • 难度
  • 共享题库
  • Codeforces
  • 英文题面
  • 题目来源
  • 题面语言

Coprime Permutation

题目描述

F. Coprime Permutation
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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 p1,p2,...,pn 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.

Input

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

The second line contains n integers p1,p2,...,pn (0≤pi≤n) where pi=0 means a gap to fill, and pi≥1 means a fixed number.

It's guaranteed that if i≠j and pi,pj≥1 then pi≠pj.

Output

Print the number of ways to fill the gaps modulo 109+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 p3=1 and p4=2. The two permutations satisfying the conditions are: (3,4,1,2,5), (5,4,1,2,3).


题目来源:fps-www.educg.net-codeforce-1-2833.xml.zip;FPS 共享题包,题包内第 628 题。保留原作者与原赛事署名。