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;
#define ll long long
#define inf 0x3f3f3f3f
#define N 100020
#define mod 1000000007
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x*f;
}
int n,a[N],du[N],col[N],len[N],cnt[N];
ll ans=1,dp[N];
bool cir[N];
inline int calc(int l1,int l2){
    return (l1<l2)+(l1<=l2);
}
int main(){
//    freopen("a.in","r",stdin);
    n=read();for(int i=1;i<=n;++i) a[i]=read(),du[a[i]]++;
    for(int i=1;i<=n;++i){
        if(col[i]) continue;int x=i;
        for(;!col[x];x=a[x]) col[x]=i;
        if(col[x]!=i) continue;//成环了，标记下环上的点
        for(;!cir[x];x=a[x]) cir[x]=1;
    }for(int i=1;i<=n;++i) if((!cir[i]&&du[i]>1)||(cir[i]&&du[i]>2)){puts("0");return 0;}
    for(int i=1;i<=n;++i){//计算foot的长度
        if(du[i]) continue;int x=i,res=0;
        while(!cir[x]) ++res,x=a[x];len[x]=res;
    }for(int i=1;i<=n;++i){//处理基环内向树
        if(!cir[i]) continue;int x=i,fir=0,firlen=0,k=0,last=0;
        while(cir[x]){
            ++k;cir[x]=0;
            if(len[x]){
                if(!fir){fir=last=k;firlen=len[x];x=a[x];continue;}
                ans=ans*calc(len[x],k-last)%mod;if(!ans){puts("0");return 0;}last=k;
            }x=a[x];
        }if(!fir) cnt[k]++;else ans=ans*calc(firlen,fir+k-last)%mod;
    }if(!ans){puts("0");return 0;}
    for(int i=1;i<=n;++i){//处理大小为i的所有环
        if(!cnt[i]) continue;dp[0]=1;int op=(i&1)+(i>1);//奇环且大于1有两种
        for(int j=1;j<=cnt[i];++j){
            dp[j]=dp[j-1]*op%mod;
            if(j>1) dp[j]=(dp[j]+(ll)(j-1)*i*dp[j-2]%mod)%mod;
        }ans=ans*dp[cnt[i]]%mod;
    }printf("%lld\n",ans);
    return 0;
}