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>

#define MAXN 100005

typedef long long lint;

using namespace std;

const int mod = 1e9 + 7;
int n, a[MAXN], val[MAXN], deg[MAXN];
int sum[MAXN];
lint f[MAXN];
bool oncir[MAXN];
int visit[MAXN];
lint ans = 1;

int read() {
    char c = getchar();
    int x = 0;
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c)) {
        x = (x << 3) + (x << 1) + c - '0';
        c = getchar();
    }
    return x;
}

void calc(int u) {
    vector<int> g;
    while (oncir[u]) {
        oncir[u] = false;
        g.push_back(u);
        u = a[u];
    }
    reverse(g.begin(), g.end());
    int first = -1, last = -1;
    for (int i = 0; i < (int)g.size(); ++i) {
        int u = g[i];
        if (val[u]) {
            if (!(~first)) {
                last = first = i;
                continue;
            }
            int l1 = val[g[last]], l2 = i - last;
            ans = ans * ((l2 > l1) + (l2 >= l1)) % mod;
            last = i;
        }
    }
    if (~first && first == last) {
        int l1 = val[g[last]], l2 = (int)g.size();
        ans = ans * ((l2 > l1) + (l2 >= l1)) % mod;
    }
    else if (~first) {
        int l1 = val[g[last]], l2 = (int)g.size() - last + first;
        ans = ans * ((l2 > l1) + (l2 >= l1)) % mod;
    }
    else
        ++sum[(int)g.size()];
}

void solve() {
    for (int i = 1; i <= n; ++i)
        if (oncir[i])
            calc(i);
    for (int i = 1; i <= n; ++i) {
        f[0] = 1;
        for (int j = 1; j <= sum[i]; ++j) {
            if ((i & 1) && i != 1)
                f[j] = f[j - 1] * 2 % mod;
            else
                f[j] = f[j - 1];
            if (j > 1)
                f[j] = (f[j] + f[j - 2] * i % mod * (j - 1) % mod) % mod;
        }
        ans = ans * f[sum[i]] % mod;
    }
}

int main() {
//    freopen("1_12.txt", "r",stdin);
    n = read();
    for (int i = 1; i <= n; ++i) {
        a[i] = read();
        ++deg[a[i]];
    }
    for (int i = 1; i <= n; ++i) {
        int u = i;
        if (visit[u])
            continue;
        while (!visit[u]) {
            visit[u] = i;
            u = a[u];
        }
        if (visit[u] != i)
            continue;
        while (!oncir[u]) {
            oncir[u] = true;
            u = a[u];
        }
    }
    for (int i = 1; i <= n; ++i)
        if ((oncir[i] && deg[i] > 2) || (!oncir[i] && deg[i] > 1)) {
            puts("0");
            return 0;
        }
    for (int i = 1; i <= n; ++i) {
        if (deg[i])
            continue;
        int u = i, d = 0;
        while (!oncir[u]) {
            u = a[u];
            ++d;
        }
        val[u] = d;
    }
    solve();
    printf("%lld\n", ans);
}