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 Return(x) { printf("%d\n",x); return ; }

typedef long long LL;

const int N=1e5+10,Mod=1e9+7;

int n,a[N],In[N],len[N],ccir[N],dp[N];

void Init() {
	scanf("%d",&n);
	for (int i=1;i<=n;++i) scanf("%d",&a[i]),In[a[i]]++;; 
}

int vis[N];
bool cir[N];

int pd(int x,int y) {
	if (y<x) return 0;
	if (y==x) return 1;
	return 2;
}

void Solve() {
	for (int i=1;i<=n;++i) {
		if (vis[i]) continue;
		int x=i;
		while (!vis[x]) vis[x]=i,x=a[x];
		if (vis[x]!=i) continue;
		while (!cir[x]) cir[x]=1,x=a[x]; 
	}
	for (int i=1;i<=n;++i) {
		if (cir[i] && In[i]>2) Return(0);
		if (!cir[i] && In[i]>1) Return(0);
	}
	for (int i=1;i<=n;++i) {
		if (In[i]) continue;
		int x=i,cnt=0; while (!cir[x]) x=a[x],cnt++;
		len[x]=cnt;
	}	
	int ans=1;
	for (int i=1;i<=n;++i) if (cir[i]) {
		int first=0,last=0,rk=0,x=i,flen;
		while (cir[x]) {
			++rk; cir[x]=0;
			if (len[x]) {
				if (!first) { first=rk; last=rk; flen=len[x]; }
				else {
					ans=1ll*ans*pd(len[x],rk-last)%Mod;
					last=rk;
				}
			}
			x=a[x];
		}
		if (!first) ccir[rk]++;else ans=1ll*ans*pd(flen,first+rk-last)%Mod;
	}
	for (int i=1;i<=n;++i) if (ccir[i]) {
		dp[0]=1; int tp=(i&1)+(i>1);
		for (int j=1;j<=ccir[i];++j) {
			dp[j]=dp[j-1]*tp%Mod;
			if (j>1) dp[j]=(dp[j]+1ll*(j-1)*i%Mod*dp[j-2])%Mod;
		}
		ans=1ll*ans*dp[ccir[i]]%Mod;
	}
	Return(ans);
}

int main() {
	Init();
	Solve();
	return 0;
}