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>
#define LL long long
using namespace std;
const int mod=1e9+7;
int fastpow(int x,int a){
	int ret=1;
	while(a){
		if(a&1) ret=(LL)ret*x%mod;
		x=(LL)x*x%mod;a>>=1;
	}
	return ret;
}

struct Combin{
	#define N 200005
	int fac[N],rv[N],facrv[N];
	Combin(){
		fac[0]=rv[1]=facrv[0]=1;
		for(int i=2;i<N;i++) rv[i]=((-(LL)(mod/i)*rv[mod%i]%mod)+mod)%mod;
		for(int i=1;i<N;i++) fac[i]=(LL)fac[i-1]*i%mod;
		for(int i=1;i<N;i++) facrv[i]=(LL)facrv[i-1]*rv[i]%mod;
	}
	int C(int r1,int n1){
		if(r1>n1) return 0;
		return fac[n1]*(LL)facrv[r1]%mod*facrv[n1-r1]%mod;
	}
	#undef N
}C;
#define N 100005
int p[N],n,cnt,in[N],len[N],vis[N];
int ans=1;
void tp(int x){
	if(len[p[x]]!=0) ans=0;
	len[p[x]]=len[x]+1;
	len[x]=-1;
	in[p[x]]--;
	if(in[p[x]]==0) tp(p[x]);
}
int sz[N];
void solve(int id){
	vis[id]=1;
	if(p[id]==id&&len[id]==0){sz[1]++;return;}
	deque<int> v;
	bool iscir=true;
	v.push_back(len[id]);
	for(int i=p[id];i!=id;i=p[i])
		vis[i]=1,v.push_back(len[i]);
	for(int i:v) if(i!=0) iscir=false;
	if(iscir){
		sz[v.size()]++;
	}else{
		while(v.back()==0) v.push_front(0),v.pop_back();
		while(!v.empty()){
			int val=v.back();v.pop_back();
			while(!v.empty() && v.back()==0) v.pop_back(),val--;
			if(val==1) continue;
			else if(val<1) ans=ans*2%mod;
			else ans=0;
		}
	}
}
int f(int j){//j = 2k
	//how many ways to matchs
	//if there k matchs in 2k points
	//ans = C(2,2k)*C(2,2k-2)...*C(2,4)*C(2,2)/(k!)
	//	=C(2k-2,2k)*C(2k-4,2k-2)...C(0,2)/(k!)
	//  =(2k)!/((2!)^k)/(k!)
	return C.fac[j]*1LL*C.facrv[j/2]%mod*fastpow(C.facrv[2],j/2)%mod;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&p[i]),in[p[i]]++;
	for(int i=1;i<=n;i++)
		if(in[i]==0&&len[i]==0)
			tp(i);
	if(ans==0) return puts("0"),0;
	for(int i=1;i<=n;i++)
		if(vis[i]==0&&len[i]>=0)
			solve(i);
	for(int i=1;i<=n;i++){
		int ansnow=0;
		if(i==1||i%2==0){
			for(int j=0;j<=sz[i];j+=2)
				ansnow = (ansnow + C.C(j,sz[i]) *1LL* f(j)%mod *fastpow(i,j/2)%mod * fastpow(1,sz[i]-j) )%mod;
		}else{
			for(int j=0;j<=sz[i];j+=2)
				ansnow = (ansnow + C.C(j,sz[i]) *1LL* f(j)%mod *fastpow(i,j/2)%mod * fastpow(2,sz[i]-j) )%mod;
		}
		ans = ans*1LL*ansnow%mod;
	}
	cout<<ans<<endl;
	return 0;
}