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 maxn 200005
#define mod 1000000007
using namespace std;
int deg[maxn],a[maxn],incy[maxn],vis[maxn],svis[maxn],n;
int chlen[maxn],cnt[maxn];
int ans=1;
int add(int a,int b){a+=b; return a>=mod?a-mod:a;}
void SolveCyc(int x)
{
	int t=x; x=a[x],svis[t]=svis[x]=1;
	int fi=0,fpos=0,la=0,len=1;
	while(1)
	{
		while(!chlen[x]&&x!=t) x=a[x],svis[x]=1,len++;
		if(chlen[x])
		{
			if(!fi) fi=x,la=len,fpos=len;
			else
			{
				int coef=(len-la>=chlen[x])+(len-la>chlen[x]);
				ans=1ll*ans*coef%mod,la=len;
			}
		}
		if(x==t) break;
		x=a[x],svis[x]=1,len++;
	}
	if(chlen[t])
	{
		if(!fi) fi=t;
		else la=len;
	}
	if(!fi) cnt[len]++;
	else
	{
		int coef=(len-la+fpos>=chlen[fi])+(len-la+fpos>chlen[fi]);
		ans=1ll*ans*coef%mod;
	}
}
int dp[maxn];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),deg[a[i]]++;
	for(int i=1;i<=n;i++)
	{
		if(vis[i]) continue;
		int nw=i; while(!vis[nw]) vis[nw]=i,nw=a[nw];
		if(vis[nw]!=i) continue;
		int t=nw; incy[nw]=1,nw=a[nw];
		while(nw!=t) incy[nw]=1,nw=a[nw];
	}
	for(int i=1;i<=n;i++)
		if(((!incy[i])&&deg[i]>=2)||deg[i]>=3) return puts("0"),0;
	for(int i=1;i<=n;i++)
	{
		if(deg[i]) continue;
		int nw=i; while(!incy[nw]) chlen[a[nw]]=chlen[nw]+1,nw=a[nw];
	}
	for(int i=1;i<=n;i++)
		if(incy[i]&&!svis[i]) SolveCyc(i);
	for(int i=1;i<=n;i++)
	{
		if(!cnt[i]) continue;
		dp[0]=1;
		for(int j=1;j<=cnt[i];j++)
		{
			if(i>1&&(i&1)) dp[j]=add(dp[j-1],dp[j-1]);
			else dp[j]=dp[j-1];
			if(j>1) dp[j]=add(dp[j],1ll*dp[j-2]*(j-1)%mod*i%mod);
		}
		ans=1ll*ans*dp[cnt[i]]%mod;
	}
	printf("%d\n",ans);
	return 0;
}