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<iostream>
#include<cstdio>
using namespace std;
#define N 200127
#define mod 1000000007
inline int M(int x){return (x>=mod)?(x-mod):x;}
inline int M1(int x){return (x<0)?(x+mod):x;}
int n,a[N],d[N],c[N],vis[N],ans,f[N],len[N],s[N];
//c:color,vis:oncircle
int main(){
	scanf("%d",&n);int i,j,x,y,p,st,la,lal;ans=1;
	for(i=1;i<=n;i++)scanf("%d",&a[i]),++d[a[i]];
	for(i=1;i<=n;i++)
	if(!c[i])
	{
		x=i;while(!c[x]){c[x]=i;x=a[x];}
		if(c[x]!=i)continue;while(!vis[x]){vis[x]=1;x=a[x];}
	}
	for(i=1;i<=n;i++)
	if((vis[i]&&(d[i]>2))||((!vis[i])&&(d[i]>1)))
	{puts("0");return 0;}
	for(i=1;i<=n;i++)
	if(!d[i]){p=0;x=i;while(!vis[x]){++p;x=a[x];}len[x]=p;}
	for(i=1;i<=n;i++)//基环树 
	if(vis[i])
	{
		x=i;p=st=la=lal=0;
		while(vis[x])
		{
			++p;vis[x]=0;
			if(len[x])
			{
				if(!st){st=la=p;lal=len[x];}
				else{ans=1ll*ans*((len[x]<(p-la))+(len[x]<=(p-la)))%mod;la=p;}
			}x=a[x];
		}
		if(st)ans=1ll*ans*((lal<(p+st-la))+(lal<=(p+st-la)))%mod;//是基环树 
		else ++s[p];
	}
	for(i=1;i<=n;i++)//正常环 
	if(s[i])
	{
		f[0]=1;const int up=s[i];
		if((i>1)&&(i&1))
		{
			for(j=1;j<=up;j++)
			f[j]=M(f[j-1]+f[j-1]),f[j]=M(f[j]+((j>1)?(1ll*f[j-2]*(j-1)%mod*i%mod):0));//就像PKUSC中的sg一样 
		}
		else
		{
			for(j=1;j<=up;j++)
			f[j]=f[j-1],f[j]=M(f[j]+((j>1)?(1ll*f[j-2]*(j-1)%mod*i%mod):0));//有i种方式 
		}ans=1ll*ans*f[up]%mod;
	}printf("%d",ans);return 0;
}