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;
int read(){
	int x=0;
	char ch=getchar();
	while (!isdigit(ch))
		ch=getchar();
	while (isdigit(ch))
		x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x;
}
const int N=100005,mod=1e9+7;
int n,a[N],in[N],size[N],vis[N],cro[N];
int q[N],head,tail;
int k[N],m;
int r[N];
void add(int &x,int y){
	if ((x+=y)>=mod)
		x-=mod;
}
int sc=0;
int Pre(int k,int n){
	return k==1?n:(k-1);
}
int solve(int n){
	int ans=1,f=0;
//	printf("solve :: n = %d   ",n);
//	for (int i=1;i<=n;i++)
//		printf(" %d",k[i]);
//	puts("");
	for (int i=1;i<=n;i++){
		if (k[i]==0)
			continue;
		f=1;
		int x=Pre(i,n);
		while (!k[x])
			x=Pre(x,n);
		int t=(i-x+n)%n;
		if (t==0)
			t+=n;
//		printf("%d :: t = %d\n",i,t);
		if (t<k[i])
			return 0;
		if (t>k[i])
			ans=2LL*ans%mod;
	}
	if (!f)
		r[n]++;
	return ans;
}
int dp[N];
int main(){
	n=read();
	memset(in,0,sizeof in);
	for (int i=1;i<=n;i++){
		in[a[i]=read()]++;
		size[i]=1;
	}
	head=tail=0;
	for (int i=1;i<=n;i++){
		if (in[i]>2)
			return puts("0"),0;
		if (in[i]==0)
			q[++tail]=i;
		if (in[i]==2)
			cro[i]=1;
	}
	while (head!=tail){
		int x=q[++head],y=a[x];
		size[y]+=size[x];
		if (!(--in[y]))
			q[++tail]=y;
	}
	for (int i=1;i<=n;i++)
		if (cro[i]&&!in[i])
			return puts("0"),0;
	int ans=1;
	memset(vis,0,sizeof vis);
	for (int i=1;i<=n;i++){
		if (in[i]==0||vis[i])
			continue;
		m=0;
		for (int x=i;!vis[x];x=a[x])
			vis[x]=1,k[++m]=size[x]-1;
		ans=1LL*ans*solve(m)%mod;
	}
	for (int i=1;i<=n;i++)
		if (r[i]>0){
			dp[0]=1,dp[1]=i>1&&(i&1)?2:1;
			for (int j=2;j<=r[i];j++)
				dp[j]=(1LL*(j-1)*i%mod*dp[j-2]+dp[j-1]*(i>1&&(i&1)?2:1))%mod;
			ans=1LL*ans*dp[r[i]]%mod;
		}
	printf("%d\n",ans);
	return 0;
}