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<cstdio>
#define maxn 100005
#define mod 1000000007
int n,a[maxn],pre[maxn],deg[maxn],cnt[maxn],f[maxn],ans=1;
bool vis[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(deg[i]>2) { printf("0\n"); return 0; }
		if(deg[i]<2||vis[i]) continue;
		int p=i;
		do
		{
			if(vis[p]) { printf("0\n"); return 0; }
			vis[p]=true,pre[a[p]]=p,p=a[p];
		}while(p!=i);
	}
	for(int i=1;i<=n;i++)
		if(!deg[i])
		{
			int p=i,l1=0,l2=0;
			while(!vis[p]) vis[p]=true,p=a[p],l1++;
			do l2++,p=pre[p]; while(deg[p]!=2);
			if(l1<l2) ans=ans*2%mod;
			else if(l1>l2) { printf("0\n"); return 0; }
		}
	for(int i=1;i<=n;i++)
		if(!vis[i])
		{
			int p=i,l=0;
			do l++,p=a[p],vis[p]=true; while(p!=i);
			cnt[l]++;
		}
	for(int i=1;i<=n;i++)
	{
		int mul=1;
		if(i!=1&&(i&1)) mul++;
		f[0]=1,f[1]=mul;
		for(int j=2;j<=cnt[i];j++) f[j]=(1ll*f[j-2]*(j-1)%mod*i%mod+1ll*f[j-1]*mul%mod)%mod;
		ans=1ll*ans*f[cnt[i]]%mod;
	}
	printf("%d\n",ans);
}