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<algorithm>
#include<cstdio>
#define mxn 1000010
#define LL long long
using namespace std;
const int mod=1e9+7;
int n,id,sl,fh,ans,a[mxn],d[mxn],l[mxn],dp[mxn],col[mxn],cir[mxn],tot[mxn];
int rd()
{
	sl=0;fh=1;
	char ch=getchar();
	while(ch<'0'||'9'<ch) {if(ch=='-') fh=-1; ch=getchar();}
	while('0'<=ch&&ch<='9') sl=sl*10+ch-'0',ch=getchar();
	return sl*fh;
}
int main()
{
//	freopen("dayinf.in","r",stdin);
//	freopen("dayinf.out","w",stdout);
	n=rd();int x;ans=1;
	for(int i=1;i<=n;++i) a[i]=rd();
	for(int i=1;i<=n;++i)
	{
		d[a[i]]++;
		x=i;for(;!col[x];col[x]=i,x=a[x]);
		if(col[x]==i) for(++id;!cir[x];cir[x]=id,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 c,i=1;i<=n;++i)
		if(!d[i])
		{
			for(c=0,x=i;!cir[x];++c,x=a[x]);
			l[x]=c;
		}
	for(int ln,st,ed,cnt,i=1;i<=n;++i)
		if(cir[i])
		{
			st=ed=cnt=0;
			for(x=i;cir[x];cir[x]=0,x=a[x])
			{
				cnt++;
				if(l[x])
				{
					if(!st) st=ed=cnt,ln=l[x];
					else ans=1ll*ans*((l[x]<cnt-ed)+(l[x]<=cnt-ed))%mod,ed=cnt;
				}
			}
			if(st) ans=1ll*ans*((ln<cnt+st-ed)+(ln<=cnt+st-ed))%mod;
			else tot[cnt]++;
		}
	dp[0]=1;
	for(int i=1;i<=n;++i)
		if(tot[i])
		{
			for(int j=1;j<=tot[i];++j)
			{
				dp[j]=1ll*dp[j-1]*((i>1&&(i&1))+1)%mod;
				if(j>1) dp[j]=(dp[j]+1ll*i*(j-1)%mod*dp[j-2])%mod;
			}
			ans=1ll*ans*dp[tot[i]]%mod;
		}
	printf("%d\n",ans);
	fclose(stdin);fclose(stdout);
	return 0;
}