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 N=100010,mo=int(1e9+7);
struct edge{int s,t,n;}e[N];
int n,a[N],h[N],d[N],vis[N],inc[N],len[N],cnt[N],fac[N],ifac[N],ans;
vector <int> V;

int qpow(int a,int b)
{
	int x=a;  a=1;
	while (b)
		{
			if (b&1)  a=1LL*a*x%mo;
			x=1LL*x*x%mo,b>>=1;
		}
	return a;
}

int C(int n,int m){return 1LL*fac[n]*ifac[m]%mo*ifac[n-m]%mo;}

int go(int x)
{
	if (vis[x])  return x;
	vis[x]=1;
	int _=go(a[x]);
	if (_)  inc[x]=1,V.push_back(x);
	return _==x?0:_;
}

int dfs(int x,int f)
{
	int _=0;
	vis[x]=1;
	for (int i=h[x],y; y=e[i].t,i; i=e[i].n)
		if ((y!=f)&&(!inc[y]))
			{
				if (_)  return -1<<30;
				else  _=dfs(y,x)+1;
			}
	return _;
}

void work()
{
	scanf("%d",&n),ans=1;
	for (int i=1; i<=n; i++)
		scanf("%d",&a[i]),e[i]=(edge){a[i],i,h[a[i]]},h[a[i]]=i,d[a[i]]++;
	for (int i=1,s; i<=n; i++)
		if (!vis[i])
			{
				V.clear(),go(i);
				for (int i=0; i<V.size(); i++)
					if ((len[i+1]=dfs(V[i],0))<0)
						puts("0"),exit(0);
				s=0;
				for (int i=1; i<=V.size(); i++)
					if (!len[i])  s++;  else  break;
				if (s==V.size())  {cnt[s]++;  continue;}
				for (int i=V.size(); i; i--)
					{
						s++;
						if (len[i])
							{
								if (s<len[i])  puts("0"),exit(0);
								if (s>len[i])  ans=2*ans%mo;
								s=0;
							}
					}
			}
	fac[0]=1;
	for (int i=1; i<=n; i++)  fac[i]=1LL*fac[i-1]*i%mo;
	ifac[n]=qpow(fac[n],mo-2);
	for (int i=n; i; i--)  ifac[i-1]=1LL*ifac[i]*i%mo;
	for (int i=1,s; i<=n; i++)
		if (cnt[i])
			{
				s=0;
				for (int j=0,_; j<=cnt[i]/2; j++)
					{
						_=1LL*C(cnt[i],2*j)*fac[2*j]%mo*ifac[j]%mo*qpow(2,mo-1-j)%mo*qpow(i,j)%mo;
						if ((i&1)&&(i>1))  _=1LL*_*qpow(2,cnt[i]-2*j)%mo;
						s=(s+_)%mo;
					}
				ans=1LL*ans*s%mo;
			}
	printf("%d",ans);
}

int main()
{
	work();
	return 0;
}