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<cstring>
using namespace std;
const int N=1e5+10,mod=1e9+7;
int n,a[N],d[N],cir[N],f[N],vis[N],sum[N],foot[N],Ans=1;
void GetTree(int x)
{
	int t=0,bs=1,fl=0;
	for(vis[x]=1,x=a[x];!fl;x=a[x])
	{
		if(vis[x]) fl=1;vis[x]=1;t++;
		if(foot[x]) bs=bs*(t<foot[x]?0:(t==foot[x]?1:2))%mod,t=0;
	}
	Ans=1ll*Ans*bs%mod;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i],d[a[i]]++;
	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]&&d[i]>2)||(!cir[i]&&d[i]>1)) return puts("0"),0;
	for(int i=1;i<=n;i++)
		if(d[i]==0)
		{
			int x=i,t=0;
			while(!cir[x]) t++,x=a[x];
			foot[x]=t;
		}
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++)
		if(cir[i]&&foot[i]&&!vis[i]) GetTree(i);

	for(int i=1;i<=n;i++)
		if(!vis[i]&&cir[i])
		{
			int x=i,t=0;
			while(!vis[x]) vis[x]=1,t++,x=a[x];
			sum[t]++;
		}
	for(int w=1,u;w<=n;w++)
	{
		f[0]=1;u=sum[w];
		if(!u) continue;
		for(int i=1;i<=u;i++)
		{
			f[i]=f[i-1]*(((w&1)&&w>1)?2:1)%mod;
			if(i>1) f[i]=(f[i]+1ll*(i-1)*f[i-2]%mod*w%mod)%mod;
		}
		Ans=1ll*Ans*f[u]%mod;
	}
	cout<<Ans<<endl;
}