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;
const int N = 200000;
const int MOD = 1e9 + 7;
int n;
int ai[N], vis[N], cir[N], cnt[N], V[N];
vector <int> bi[N];
int ans = 1;
int f[N], fac[N], inv[N];
int powi(int a, int b)
{
    int c = 1;
    for (; b; b >>= 1, a = 1ll * a * a % MOD)
        if (b & 1) c = 1ll * c * a % MOD; return c;
}
int C(int a, int b)
{
    return 1ll * fac[a] * inv[b] % MOD * inv[a - b] % MOD;
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i)
        scanf("%d", &ai[i]), bi[ai[i]].push_back(i);
    for (int i = 1; i <= n; ++ i)
        if (!vis[i])
        {
            int p = i;
            for (; !vis[p]; p = ai[p]) vis[p] = i;
            if (vis[p] == i)
            for (; !cir[p]; p = ai[p]) cir[p] = 1;
        }
    for (int i = 1; i <= n; ++ i)
        if (bi[i].size() - cir[i] > 1)
            return puts("0"), 0;
    for (int i = 1; i <= n; ++ i)
        if (bi[i].size() > 1 && !cir[bi[i][1]])
            swap(bi[i][0], bi[i][1]);
    for (int i = 1; i <= n; ++ i) vis[i] = 0;
    for (int i = 1; i <= n; ++ i)
        if (cir[i] && !vis[i])
        {
            int l = 0, G = 0;
            for (int j = i; !vis[j]; j = ai[j])
            {
                l ++;
                vis[j] = 1;
                cnt[l] = 0;
                if (!cir[bi[j][0]])
                    for (int k = j; bi[k].size(); k = bi[k][0])
                        cnt[l] ++, G = 1;
            }
            if (!G)
            {
                V[l] ++;
                continue;
            }
            for (int j = 1; j <= l; ++ j) cnt[j + l] = cnt[j];
            int x = 1;
            while (!cnt[x]) x ++;
            for (int j = x + 1, k = x; j <= x + l; ++ j)
                if (cnt[j])
                {
                    if (cnt[j] > j - k) return puts("0"), 0;
                    else if (cnt[j] < j - k) ans = 2ll * ans % MOD;
                    k = j;
                }
        }
    f[0] = 1;
    for (int i = 1; i <= n; ++ i) f[i] = 1ll * f[i - 1] * (2 * i - 1) % MOD;
    fac[0] = 1;
    for (int i = 1; i <= n; ++ i) fac[i] = 1ll * fac[i - 1] * i % MOD;
    inv[n] = powi(fac[n], MOD - 2);
    for (int i = n - 1; ~i; -- i) inv[i] = 1ll * inv[i + 1] * (i + 1) % MOD;
    for (int i = 1; i <= n; ++ i)
    {
        int res = 0;
        for (int j = 0, k = 1; j <= V[i] / 2; ++ j, k = 1ll * k * i % MOD)
            res = (res + 1ll * C(V[i], j * 2) * f[j] % MOD * k % MOD * (i > 1 && (i & 1)? powi(2, V[i] - j * 2): 1)) % MOD;
        ans = 1ll * ans * res % MOD;
    }
    printf("%d\n", ans);
}