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;
const int N=1e5+10,mod=1e9+7;

int n,ans=1;
int t[N],a[N],vs[N],d[N],dr[N],f[N];
bool cir[N];

inline int ad(int x,int y){x+=y;return x>=mod?x-mod:x;}

void sol(int x)
{
	int nw=0,fi=0,sc,pre;
	for(;cir[x];x=a[x]){
		++nw;cir[x]=false;
		if(!dr[x]) continue;
		if(!fi) {fi=sc=nw;pre=dr[x];}
		else{
			if(nw-sc<dr[x]) ans=0;
			else if(nw-sc>dr[x]) ans=ad(ans,ans);
			sc=nw;
		}
	}
	if(!fi) t[nw]++;
	else{
		nw=fi-sc+nw;
		if(nw<pre) ans=0;
		else if(nw>pre) ans=ad(ans,ans);
	}
}

int main(){
	int i,j,k;
	
	scanf("%d",&n);
	for(i=1;i<=n;++i) {scanf("%d",&a[i]);d[a[i]]++;}
	for(i=1;i<=n;++i) if(!vs[i]){
		vs[i]=i;
		for(j=a[i];!vs[j];j=a[j]) vs[j]=i;
		if(vs[j]^i) continue;
		for(;!cir[j];j=a[j]) cir[j]=true;
	}
	
	for(i=1;i<=n;++i)
	 if((cir[i] && d[i]>2)||((!cir[i])&& d[i]>1))
	   {puts("0");return 0;}
	
	for(i=1;i<=n;++i) if(!d[i]){
		for(k=0,j=i;(!cir[j]);j=a[j]) k++;
		dr[j]=k;
	}
	
	for(i=1;i<=n;++i) if(cir[i]) sol(i);
	if(!ans) {puts("0");return 0;}
	
	f[0]=1;
	for(i=1;i<=n;++i) if(t[i]){
		for(j=1;j<=t[i];++j){
			if(i>1 && (i&1)) f[j]=ad(f[j-1],f[j-1]);
			else f[j]=f[j-1];
			if(j>1) f[j]=ad(f[j],(ll)f[j-2]*(j-1)*i%mod);
		}
		ans=(ll)ans*f[t[i]]%mod;
	}
	printf("%d",ans);
	return 0;
}