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;
const int maxn=2e5,mod=1e9+7;
int n,ctt,tmp,a[maxn],d[maxn],cnt[maxn],cir_cnt[maxn];
long long ans=1,f[maxn];
bool vis[maxn];
vector <int> to[maxn];
queue <int> q;
void dfs(int now){
	if(cnt[now]!=1) tmp=now;
	vis[now]=true;ctt++;
	int siz=to[now].size();
	for(int i=0;i<siz;i++){
		int u=to[now][i];
		if(vis[u]==true) continue;
		dfs(u);
	}
}
int work(int now){
	int siz=to[now].size(),len;
	for(int i=0;i<siz;i++){
		int u=to[now][i];
		if(u==tmp){len=cnt[tmp]-2;continue;}
		len=work(u);
	}
	if(cnt[now]==1){return len-1;}
	else{
		if(len>=1){ans=0;}
		if(len<=-1){ans=ans*2%mod;}
		return cnt[now]-2;
	}
}
void Go(int now){
	ctt=0;tmp=0;
	dfs(now);
	if(!tmp){cir_cnt[ctt]++;}
	else{work(tmp);}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){cnt[i]=1;scanf("%d",&a[i]);to[i].push_back(a[i]);d[a[i]]++;}
	for(int i=1;i<=n;i++){if(d[i]==0) q.push(i);}
	while(!q.empty()){
		int now=q.front();q.pop();
		int siz=to[now].size();
		vis[now]=true;
		for(int i=0;i<siz;i++){
			int u=to[now][i];
			d[u]--;
			if(cnt[u]!=1) ans=0;
			else cnt[u]+=cnt[now];
			if(d[u]==0) q.push(u);
		}
	}
	for(int i=1;i<=n;i++){if(!vis[i]){Go(i);}}
	for(int i=1;i<=n;i++){
		f[0]=1;
		int opt=((i&1)&&(i!=1))?2:1,k=cir_cnt[i];
		for(int j=1;j<=k;j++){f[j]=0;}
		for(int j=0;j<k;j++){
			f[j+1]=(f[j+1]+f[j]*opt)%mod;
			f[j+2]=(f[j+2]+f[j]*(k-j-1)%mod*i%mod)%mod;
		}
		ans=ans*f[k]%mod;
	}
	printf("%lld\n",ans);
	return 0;
}