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 <bits/stdc++.h>

using namespace std;

#define RI register int

int read() {
  int q = 0;
  char ch = ' ';
  while (ch < '0' || ch > '9') ch = getchar();
  while (ch >= '0' && ch <= '9') q = q * 10 + ch - '0', ch = getchar();
  return q;
}

const int mod = 1e9 + 7, N = 100005;

int n, ans;
int a[N], du[N], cir[N], vis[N], footL[N], sum[N], f[N];

int qm(int x) { return x >= mod ? x - mod : x; }
void workcir(int x) {
  int now = 0, fr = 0, ed = 0, frL = 0;
  while (cir[x]) {
    ++now, cir[x] = 0;
    if (footL[x]) {
      if (!fr)
        ed = fr = now, frL = footL[x];
      else {
        int kl = (footL[x] < now - ed) + (footL[x] <= now - ed);
        ans = 1LL * ans * kl % mod, ed = now;
      }
    }
    x = a[x];
  }
  if (!fr)
    ++sum[now];
  else {
    int kl = (frL < now - ed + fr) + (frL <= now - ed + fr);
    ans = 1LL * ans * kl % mod;
  }
}

void work() {
  for (RI i = 1; i <= n; ++i) {
    if (du[i]) continue;
    int x = i, len = 0;
    while (!cir[x]) x = a[x], ++len;
    footL[x] = len;
  }
  ans = 1;
  for (RI i = 1; i <= n; ++i)
    if (cir[i]) workcir(i);
  for (RI i = 1; i <= n; ++i) {
    if (!sum[i]) continue;
    f[0] = 1;
    for (RI j = 1; j <= sum[i]; ++j) {
      if (i > 1 && (i & 1))
        f[j] = qm(f[j - 1] + f[j - 1]);
      else
        f[j] = f[j - 1];
      if (j > 1) f[j] = qm(f[j] + 1LL * f[j - 2] * (j - 1) % mod * i % mod);
    }
    ans = 1LL * ans * f[sum[i]] % mod;
  }
}

int main() {
  n = read();
  for (RI i = 1; i <= n; ++i) a[i] = read(), ++du[a[i]];
  for (RI i = 1; i <= n; ++i) {
    if (vis[i]) continue;
    int x = i;
    while (!vis[x]) vis[x] = i, x = a[x];
    if (vis[x] != i) continue;
    while (!cir[x]) cir[x] = 1, x = a[x];
  }
  for (RI i = 1; i <= n; ++i)
    if ((cir[i] && du[i] > 2) || (!cir[i] && du[i] > 1)) return puts("0"), 0;
  work();
  printf("%d\n", ans);
  return 0;
}