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:
/*
https://blog.csdn.net/litble/article/details/83118814

图论神啊，好题好题好题！！！
i 向 pi 连条边，构成的图简化以后就都是 “i 向 ai 连条边” 这个图了！！！

注意：是由一个环和若干条指向环的链组成的基环内向树，至于为什么是链，详见样例4

现在手上只有 a，那么就**倒推**有多少种可能图吧
*/
#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
using namespace std;

const int mod = 1e9 + 7, N = 1e5 + 10;
typedef long long ll;
int n, a[N], deg[N], vis[N], cir[N], L[N], sum[N];
ll ans, f[N];

void calc(int x) {
    int now = 0, fr = 0, ed = 0, l = 0;
    // fr: 第一个脚的位置  ed: 上一个脚的位置  l: 第一个脚的长度  now: 当前节点是从 x 开始走环走到的第几个点
    while (cir[x]) {
        ++now, cir[x] = 0;
        if (L[x]) {
            if (!fr) ed = fr = now, l = L[x];
            else {
                int tmp = (L[x] < now - ed) + (L[x] <= now - ed);
                ans = 1ll * ans * tmp % mod, ed = now;
            }
        }
        x = a[x];
    }
    if (!fr) ++sum[now];
    else {
        int tmp = (l < now - ed + fr) + (l <= now - ed + fr);
        ans = 1ll * ans * tmp % mod;
    }
}

void solve() {
    rep(i, 1, n) {
        if (deg[i]) continue;
        int x = i, len = 0; while (!cir[x]) ++len, x = a[x];
        L[x] = len;
    }
    ans = 1;
    rep(i, 1, n) if (cir[i]) calc(i);

    // 计算每种长度的简单环的方案
    rep(i, 1, n) {
        f[0] = 1;
        rep(j, 1, sum[i]) {
            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] * (j - 1) % mod * i % mod) % mod;
        }
        ans = 1ll * ans * f[sum[i]] % mod;
    }
}

int main() {
    cin >> n;
    rep(i, 1, n) scanf("%d", &a[i]), ++deg[a[i]];
    rep(i, 1, n) {
        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];
    }
    rep(i, 1, n)
        if ((!cir[i] && deg[i] > 1) || (cir[i] && deg[i] > 2)) return puts("0"), 0;
    solve();
    printf("%lld\n", ans);
    return 0;
}