Problem: You are given an integer sequence a of length N. How many permutations p of the integers 1 through N satisfy the following condition?

* For each 1 ≤ i ≤ N, at least one of the following holds: p_i = a_i and p_{p_i} = a_i.



Find the count modulo 10^9 + 7.

Constraints

* 1 ≤ N ≤ 10^5
* a_i is an integer.
* 1 ≤ a_i ≤ N

Input

The input is given from Standard Input in the following format:


N
a_1 a_2 ... a_N


Output

Print the number of the permutations p that satisfy the condition, modulo 10^9 + 7.

Examples

Input

3
1 2 3


Output

4


Input

2
1 1


Output

1


Input

3
2 1 1


Output

2


Input

3
1 1 1


Output

0


Input

13
2 1 4 3 6 7 5 9 10 8 8 9 11


Output

6

Solution (in CPP):

Solution:
#include <cstdio>
#include <algorithm>
using namespace std;
const int md=1000000007,MX=100100;
int n,i,j,k,cc,d,r=1,cur,all[MX],fi[MX],la[MX],a[MX],b[MX],c[MX],cnt[MX],cyc[MX],comp[MX],v[MX],gv[MX];
long long f[MX],g[MX];
bool u[MX],w[MX],ic[MX],was;
int dfs(int i, int d) {
  b[d]=i;
  u[i]=true;
  w[i]=true;
  if (w[a[i]]) {
    c[i]=++cc;
    cyc[cc]=1;
    fi[cc]=cur;
    ic[a[i]]=true;
    all[cur++]=a[i];
    for (int j=d; b[j]!=a[i]; j--, cyc[cc]++) {
      ic[b[j]]=true;
      all[cur++]=b[j];
    }
    la[cc]=cur;
  } else if (u[a[i]]) c[i]=c[a[i]]; else c[i]=dfs(a[i],d+1);
  w[i]=false;
  comp[c[i]]++;
  return c[i];
}
int main() {
  scanf("%d",&n);
  for (f[0]=g[0]=i=1; i<=n; i++) {
    scanf("%d",&a[i]);
    v[a[i]]++;
    f[i]=(((i>1)?(i-1)*f[i-2]:0LL)+f[i-1]*2)%md;
    g[i]=(((i>1)?(i-1)*g[i-2]:0LL)+g[i-1])%md;
  }
  for (i=1; i<=n; i++) if (v[i]==0) dfs(i,1);
  for (i=1; i<=n; i++) if (u[i]) {
    if (v[i]>2) { puts("0"); return 0; }
    if (!ic[i]) {
      if (v[i]>1) { puts("0"); return 0; }
      gv[a[i]]=i;
    }
  }
  for (i=1; i<=cc; i++) {
    if (comp[i]>2*cyc[i]) { puts("0"); return 0; }
    was=false;
    for (cur=0, j=fi[i]; j<la[i]; j++, cur--) {
      k=all[j];
      int cz=0;
      for (int e=gv[k]; e!=0; e=gv[e]) cz++;
      if (cz>0) {
        if (was) {
          if (cur>0) { puts("0"); return 0; }
          if (cur<0) r=(r*2)%md;
        } else was=true;
        cur=cz;
      }
    }
    for (j=fi[i]; j<la[i]; j++, cur--) {
      k=all[j];
      int cz=0;
      for (int e=gv[k]; e!=0; e=gv[e]) cz++;
      if (cz>0) {
        if (cur>0) { puts("0"); return 0; }
        if (cur<0) r=(r*2)%md;
        cur=cz;
        break;
      }
    }
  }
  for (i=1; i<=n; i++) if (!u[i]) {
    for (j=i, k=0; !u[j]; j=a[j], k++) u[j]=true;
    cnt[k]++;
  }
  r=(r*g[cnt[1]])%md;
  for (j=2; j<=n; j+=2) {
    for (i=1; i<=cnt[j]; i++) g[i]=(((i>1)?((i-1)*g[i-2])%md*j:0LL)+g[i-1])%md;
  r=(r*g[cnt[j]])%md;
  }
  for (j=3; j<=n; j+=2) {
    for (i=1; i<=cnt[j]; i++) f[i]=(((i>1)?((i-1)*f[i-2])%md*j:0LL)+f[i-1]*2)%md;
  r=(r*f[cnt[j]])%md;
  }
  printf("%d\n",r);
  return 0;
}