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 N 100005
#define ll long long
#define P 1000000007
using namespace std;
int n,fa[N],b[N],rd[N],fl[N],sum[N];
void biu()
{
	puts("0");
	exit(0);
}
void dfs(int x)
{
	if (fl[fa[x]]) biu();
	rd[fa[x]]--;fl[fa[x]]=fl[x]+1;rd[x]=-1;
	if (rd[fa[x]]==0) dfs(fa[x]);
}
int F(int x,int k)
{
	static int f[N];
	f[0]=1;f[1]=2;
	for (int i=2;i<=x;i++)
		f[i]=(f[i-1]*2+(ll)f[i-2]*(i-1)%P*k)%P;
	return f[x];
}
int G(int x,int k)
{
//	cout<<x<<' '<<k<<endl;
	static int g[N];
	g[0]=1;g[1]=1;
	for (int i=2;i<=x;i++)
		g[i]=(g[i-1]+(ll)g[i-2]*(i-1)%P*k)%P;
	return g[x];
}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
		scanf("%d",&fa[i]),rd[fa[i]]++;
	for (int i=1;i<=n;i++)
		if (rd[i]==0) dfs(i);
	int Ans=1;
	for (int i=1;i<=n;i++)
		if (rd[i]==1)
		{
			int x=i,y=fa[i],cnt=0,flag=0;
			b[++cnt]=fl[i];
			if (fl[i]) flag=cnt;
			for (;y!=i;y=fa[y],x=fa[x])
			{
				b[++cnt]=fl[y];rd[y]=0;
				if (fl[y]) flag=cnt;
			}
			//cout<<cnt<<' '<<flag<<endl;
			if (!flag) sum[cnt]++;
			else
			{
				flag=flag-cnt;
				for (int j=1;j<=cnt;j++)
				{
					//cout<<b[j]<<endl;
					if (b[j])
					{
						if (b[j]>j-flag) biu();
						if (b[j]<j-flag) Ans=Ans*2%P;
						flag=j;
					}
				}
			}
		}
	//	cout<<Ans<<endl;
	for (int i=1;i<=n;i++)
	{
	//	cout<<i<<' '<<sum[i]<<endl;
		if ((i&1)&&i!=1) Ans=(ll)Ans*F(sum[i],i)%P;
		else Ans=(ll)Ans*G(sum[i],i)%P;
	}
	printf("%d\n",Ans);
}