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<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
vector<int>A[110000];
int n,x[110000],pd[110000],len,B[110000],num[110000],f[110000];
map<long long,int>M;
const int mo=1e9+7;
void dfs(int k){
	if (pd[k]) return;
	pd[k]=1; B[++len]=k;
	dfs(x[k]);
	for (int i=0;i<A[k].size();i++) dfs(A[k][i]);
}
int getans(int k1,int k2,int k3){
	long long st=1ll*k1*n+k2;
	if (M.count(st)) return M[st];
	int ans=0;
	if (A[k1].size()+A[k2].size()>2||A[k1].size()>1||(A[k1].size()==0&&A[k2].size()==0)){
		M[st]=0; return 0;
	}
	int flag=0;
	for (int i=0;i<A[k1].size();i++) if (A[k1][i]==k3) flag=1;
	for (int i=0;i<A[k2].size();i++) if (A[k2][i]==k3) flag=2;
	if (flag==1){
		ans=1;
		if (A[k2].size()>0&&A[A[k2][0]].size()>0) ans=0;
	//	cout<<"getans1 "<<k1<<" "<<k2<<" "<<k3<<" "<<ans<<endl;
		M[st]=ans; return ans;
	}
	if (flag==2){
		int ex=0; ans=1;
		if (A[k1].size()>0) ex=A[k1][0];
		if (ex) ans=0;
		if (A[k2].size()>1) ex=A[k2][0]+A[k2][1]-k3;
		if (ex&&A[ex].size()>0) ans=0;
	//	cout<<"getans2 "<<k1<<" "<<k2<<" "<<k3<<" "<<ans<<endl;
		M[st]=ans; return ans;
	}
	if (A[k1].size()==0){
		if (A[k2].size()==1){
			ans=(ans+getans(0,A[k2][0],k3))%mo;
		} else {
			ans=(ans+getans(A[k2][0],A[k2][1],k3))%mo;
			ans=(ans+getans(A[k2][1],A[k2][0],k3))%mo;
		}
	} else if (A[k2].size()==0) 
		ans=(ans+getans(0,A[k1][0],k3))%mo;
	else ans=(ans+getans(A[k1][0],A[k2][0],k3))%mo;
	M[st]=ans;
//	cout<<"getans "<<k1<<" "<<k2<<" "<<k3<<" "<<ans<<endl;
	return ans;
}
int solve(){
	int flag=0,where=0; M.clear();
	for (int i=1;i<=len;i++) if (A[B[i]].size()!=1) flag=1;
	//for (int i=1;i<=len;i++) cout<<B[i]<<" "; cout<<endl;
	if (flag==0){
		num[len]++; return 1;
	}
	for (int i=1;i<=len;i++) if (A[B[i]].size()==2) where=B[i];
	int ans=getans(0,where,where);
	return ans;
}
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&x[i]),A[x[i]].push_back(i);
	for (int i=1;i<=n;i++) if (A[i].size()>2){
		printf("0\n"); return 0;
	}
	int ans=1;
	for (int i=1;i<=n;i++) if (pd[i]==0){
		len=0; dfs(i);
		ans=1ll*ans*solve()%mo;
	}
	//cout<<ans<<endl;
	for (int i=1;i<=n;i++){
		f[0]=1; f[1]=1;
		if ((i&1)&&(i>1)) f[1]=2;
		for (int j=2;j<=num[i];j++)
			f[j]=(1ll*f[j-2]*(j-1)%mo*i+1ll*f[j-1]*(1+(i&1)-(i==1)))%mo;
		ans=1ll*ans*f[num[i]]%mo;
	}
	cout<<ans<<endl;
	return 0;
}