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;
template<typename T>inline T read(){
	T f=0,x=0;char c=getchar();
	while(!isdigit(c)) f=c=='-',c=getchar();
	while(isdigit(c)) x=x*10+c-48,c=getchar();
	return f?-x:x;
}
namespace run{
	const int N=1e5+9,mod=1e9+7;
	inline int add(int x,int y){return x+y>=mod?x-mod+y:x+y;}
	int n,a[N],cir[N],vis[N],deg[N],len[N],top[N],sum[N],f[N];

	int ans=1;
	inline void solve(int x){
		int tmp=a[x],las=0,now=0,ret=1;
		while(cir[tmp]==1){
			now++;
			if(len[tmp]){
				int res=(now-las>=len[tmp])+(now-las>len[tmp]);
				ret=1LL*ret*res%mod,las=now;
			}
			cir[tmp]=2,tmp=a[tmp];
		}
		ans=1LL*ans*ret%mod;
	}
	int main(){
		n=read<int>();
		for(int i=1;i<=n;i++) deg[a[i]=read<int>()]++;
		
		for(int i=1;i<=n;i++){
			int tmp=i;
			while(!vis[tmp]) vis[tmp]=i,tmp=a[tmp];
			if(vis[tmp]==i){
				int now=tmp;
				do{cir[now]=1,now=a[now];}while(now!=tmp);
			}
		}

		for(int i=1;i<=n;i++)
			if((cir[i] && deg[i]>2) || (!cir[i] && deg[i]>1)) puts("0"),exit(0);
		for(int i=1;i<=n;i++) if(!deg[i]){
			int tmp=i,siz=0;
			while(!cir[tmp]) siz++,tmp=a[tmp];
			len[tmp]=siz,top[i]=tmp;
		}
		for(int i=1;i<=n;i++) if(!deg[i] && cir[top[i]]==1) solve(top[i]);

		for(int i=1;i<=n;i++) if(cir[i]==1){
			int tmp=i,siz=0;
			while(cir[tmp]==1) cir[tmp]=2,siz++,tmp=a[tmp];
			sum[siz]++;
		}

		for(int i=1;i<=n;i++) if(sum[i]){
			f[0]=1;
			for(int j=1;j<=sum[i];j++){
				if(i>1 && (i&1)) f[j]=add(f[j-1],f[j-1]);
				else f[j]=f[j-1];
				if(j>1) f[j]=(1LL*f[j-2]*i%mod*(j-1)+f[j])%mod;
			}
			ans=1LL*ans*f[sum[i]]%mod;
		}
		printf("%d\n",ans);
		return 0;
	}
}
int main(){
#ifdef my
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
#endif
	return run::main();
}