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;
#define ll long long
#define f(a,b,c) for(int a=(b);a<=(c);++a)
const int mod=1e9+7,maxn=1e5+5;
int a[maxn],d[maxn],ci[maxn],vis[maxn],fl[maxn],sum[maxn],f[maxn];
int add(int a,int b){a+=b;return a>=mod?a-mod:a;}
int n,ans=1;
#define GG exit((puts("0"),0))
void solve(int x)//基环树 
{
	int cur,ths,lst,fst;
	cur=ths=lst=fst=0;
	while(ci[x])
	{
		++cur,ci[x]=0;
		if(fl[x])
		{
			if(ths==0)ths=lst=cur,fst=fl[x];
			else
			{
				if(fl[x]>cur-lst)GG;
				if(fl[x]==cur-lst)ans=ans;
				if(fl[x]<cur-lst)ans=add(ans,ans);
				lst=cur;
			}
		}
		x=a[x];
	} 
	if(!ths)sum[cur]++;
	else
	{
		if(fst>cur-lst+ths)GG;
		if(fst==cur-lst+ths)ans=ans;
		if(fst<cur-lst+ths)ans=add(ans,ans);
	}
}
int main()
{
	scanf("%d",&n);
	f(i,1,n)scanf("%d",a+i),d[a[i]]++;
	int x,l;
	f(i,1,n)
	{
		if(!vis[i])
		{
			for(x=i;!vis[x];vis[x]=i,x=a[x]);
			if(vis[x]!=i)continue;
			while(!ci[x])ci[x]=1,x=a[x];
		}
	}
	f(i,1,n){
		if(ci[i]&&d[i]>=3)GG;
		if(!ci[i]&&d[i]>=2)GG;
	}
	f(i,1,n)
	{
		if(d[i])continue;
		for(x=i,l=0;!ci[x];x=a[x],l++);
		fl[x]=l;
	}
    f(i,1,n)if(ci[i])solve(i);//基环树
    f(i,1,n)//简单环
	{
		f[0]=1;
		f(j,1,sum[i])
		{
			if(i>1&&i%2==1)f[j]=add(f[j-1],f[j-1]);
			else f[j]=f[j-1];
			if(j>1)f[j]=add(f[j],(ll)f[j-2]*(j-1)%mod*i%mod);
		}
		ans=(ll)ans*f[sum[i]]%mod;
	} 
	printf("%d",ans); 
 }