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 <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int Q=1<<17,MOD=1e9+7;
inline int add(int a,int b)
{a+=b;return a>=MOD?a-MOD:a;}
inline int mul(int a,int b)
{return 1LL*a*b%MOD;}
int a[Q];
int vis[Q];
int pi=1,maxn=0;
int val[Q];
int cir[Q];
void dfs(int x,int Time)
{
    if(vis[x]){
        if(vis[x]!=Time||cir[x])return;
        cir[x]=1;
        for(int t=a[x];t!=x;t=a[t])
            cir[t]=1;
        return;
    }
    vis[x]=Time;
    dfs(a[x],Time);
}
int in[Q];
#define GG return puts("0")&0
int f[Q];
int Ga(int x)
{return cir[x]?x:(a[x]=Ga(a[x]));}
int len[Q];
int l[Q];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]),++in[a[i]];
    for(int i=1;i<=n;i++)
        if(in[i]>2)GG;
    for(int i=1;i<=n;i++)
        if(!vis[i])dfs(i,i);
    for(int i=1;i<=n;i++){
        if(!cir[i])
            if(in[i]>1)GG;
        ++len[Ga(i)];
    }
    for(int i=1;i<=n;i++)
    if(cir[i]&&vis[i]!=-1){
        int mx=0;
        for(int t=i;vis[t]!=-1;t=a[t]){
            vis[t]=-1;
            l[++mx]=len[t]-1;
        }
        for(int i=1;i<=mx;i++)
            l[mx+i]=l[i];
        int lst=998244353,mus=0;
        for(int i=(mx<<1);i;--i)
            if(l[i]){
                if(lst-i<mus)GG;
                if(lst-i>mus&&lst>mx&&lst<=(mx<<1))pi=mul(pi,2);
                lst=i;
                mus=l[i];
            }
        if(lst>n)val[++maxn]=mx;
    }
    sort(val+1,val+maxn+1);
    f[0]=1;
    for(int i=1,had=0;i<=maxn;i++){
        if(val[i]==val[i-1])++had;
        else had=0;
        f[i]=add(mul(f[i-1],((val[i]&1)&(val[i]>1))+1),i==1?0:mul(mul(had,val[i]),f[i-2]));
    }
    printf("%d",mul(f[maxn],pi));
    return 0;
}