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;

#define int long long

const int mod=1000000007,N=100005;

bool in[N];
int vis[N],a[N],du[N],len[N],num[N],f[N];

signed main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
//	ios::sync_with_stdio(false);
	int n,ans=1;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
	//	cin>>a[i];
		scanf("%lld",&a[i]);
		du[a[i]]++;
	}
	for(int i=1;i<=n;i++)
	{
		if(!vis[i])
		{
			int p=i;
			while(!vis[p])
			{
				vis[p]=i;
				p=a[p];
			}
			if(vis[p]==i)
			{
				while(!in[p])
				{
					in[p]=true;
					p=a[p];
				}
			}
		}
	}
//	return 0;
	for(int i=1;i<=n;i++)
	{
		//	cout<<"W "<<i<<" "<<p<<endl;
		if(du[i]==0)
		{
			int p=i,res=0;
			while(!in[p])
			{
				++res;
				p=a[p];
			//	if(res>100000) break;
			}
			//cout<<"N "<<p<<" "<<in[11]<<endl;
			len[p]=res;
		}
	}
//	return 0;
	for(int i=1;i<=n;i++)
	{
		if((in[i]&&du[i]>2)||(in[i]==false&&du[i]>1))
		{
			cout<<0;
			return 0;
		}
	}
//	return 0;
	for(int i=1;i<=n;i++)
	{
		if(in[i])
		{
			int p=i,res=0,pos=0,sum;
			while(in[p])
			{
				++res;
				if(len[p])
				{
					if(!pos) 
					{
						pos=p;
						sum=res;
					}
					else 
					{
				//		cout<<"P "<<p<<" "<<len[p]<<" "<<res<<endl;
						if(res>len[p]) ans=ans*2%mod;
						else if(res<len[p]) ans=0;
					}
					res=0;
				}
				in[p]=false;
				p=a[p];
			}
			if(pos)
			{
				res+=sum;
			//	cout<<"Q "<<pos<<" "<<len[pos]<<" "<<res<<endl;
				if(res>len[pos]) ans=ans*2%mod;
				else if(res<len[pos]) ans=0;
			}
			else num[res]++;
		}
	}
//	cout<<ans<<endl;
	for(int i=1;i<=n;i++)
	{
		if(num[i])
		{
			f[0]=1;
			for(int j=1;j<=num[i];j++)
			{
				if(i%2==1&&i!=1) f[j]=f[j-1]*2%mod;
				else f[j]=f[j-1];
				if(j-2>=0) f[j]=(f[j]+(j-1)*i%mod*f[j-2]%mod)%mod;
			}
		//	cout<<i<<" "<<f[num[i]]<<endl;
			ans=ans*f[num[i]]%mod;
		}
	}
	cout<<ans;
	return 0;
}