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;

typedef long long ll;

int N;
vector<int> G[100010],ele;
int A[100010];
bool vis[100010];
bool loop[100010];
int len[100010];
int par[100010];
int num[100010];
int nxt[100010];
int cnt;
ll ans = 1;
ll dp[100010];
ll mod = 1000000007;

void DFS(int v)
{
    if(vis[v])return;
    vis[v] = true;
    ele.push_back(v);
    for(int i = 0; i < G[v].size(); i++)DFS(G[v][i]);
    DFS(par[v]);
    return;
}

int main()
{
    scanf("%d",&N);
    for(int i = 0; i < N; i++)
    {
        int a;
        scanf("%d",&a);
        G[a].push_back(i + 1);
        par[i + 1] = a;
    }

    for(int i = 1; i <= N; i++)if(!vis[i])
    {
        cnt = 0;
        ele.clear();
        DFS(i);
        int now = i;
        for(int j = 0; j < ele.size(); j++)now = par[now];
        for(int j = 0; j < ele.size(); j++)
        {
            if(!loop[now])cnt++;
            loop[now] = true;
            now = par[now];
        }
        if(cnt == ele.size())
        {
            num[cnt]++;
            continue;
        }
        int sum = 1;
        for(int j = 0; j < ele.size() * 2; j++)
        {
            nxt[now] = sum;
            sum++;
            if(G[now].size() == 2)sum = 1;
            now = par[now];
        }
        for(int j = 0; j < ele.size(); j++)
        {
            if(G[ele[j]].size() >= 3)ans = 0;
            if(!loop[ele[j]] && G[ele[j]].size() >= 2)ans = 0;
            if(G[ele[j]].size() == 0)
            {
                int l = 0;
                int tmp = ele[j];
                while(!loop[tmp])
                {
                    l++;
                    tmp = par[tmp];
                }
                len[tmp] = l;
            }
        }
        for(int j = 0; j < ele.size(); j++)
        {
            int tmp = ele[j];
            if(!loop[tmp] || G[tmp].size() == 1)continue;
            if(nxt[tmp] < len[tmp])ans = 0;
            if(nxt[tmp] > len[tmp])ans *= 2;
            ans %= mod;
        }
    }

    for(int i = 1; i <= N; i++)
    {
        for(int j = 0; j <= num[i]; j++)dp[j] = 0;
        dp[num[i]] = 1;
        for(int j = num[i]; j > 0; j--)
        {
            dp[j - 1] += dp[j];
            dp[j - 1] %= mod;
            if(j - 2 >= 0)dp[j - 2] += dp[j] * (ll)(j - 1) % mod * (ll)i % mod;
            dp[j - 2] %= mod;
            if(i % 2 && i > 1)dp[j - 1] += dp[j];
            dp[j - 1] %= mod;
        }
        ans *= dp[0];
        ans %= mod;
    }

    printf("%lld\n",ans);
    return 0;
}