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>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
#define MOD 1000000007
#define MAX 100100
#define ll long long
inline int read()
{
	int x=0;bool t=false;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')t=true,ch=getchar();
	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
	return t?-x:x;
}
int n,ans=1;
int a[MAX],dg[MAX];
bool cir[MAX];
int col[MAX],foot[MAX],cnt[MAX];
int f[MAX];
int main()
{
	n=read();
	for(int i=1;i<=n;++i)a[i]=read(),++dg[a[i]];
	for(int i=1;i<=n;++i)
	{
		if(col[i])continue;
		int x=i;
		for(;!col[x];x=a[x])col[x]=i;
		if(col[x]!=i)continue;//circle with foot
		for(;!cir[x];x=a[x])cir[x]=true;//circle
	}
	for(int i=1;i<=n;++i)//illegal part 
		if((cir[i]&&dg[i]>2)||(!cir[i]&&dg[i]>1)){puts("0");return 0;}
	for(int i=1;i<=n;++i)
	{
		if(dg[i])continue;//start of a foot do not have egde in
		int x=i,len=0;
		while(!cir[x])x=a[x],++len;
		foot[x]=len;//record length
	}
	for(int i=1;i<=n;++i)//calculate answer of circle with feet
	{
		if(!cir[i])continue;//calculate circles
		int x=i,pts=0,st=0,l1=0,fr=0;
		//st:last root of foot,fr:first root of foot,l1:length of the first foot
		//pts:number of the node in the circle
		while(cir[x])
		{
			++pts;cir[x]=false;
			if(foot[x])//a foot in the circle
			{
				if(!fr)st=fr=pts,l1=foot[x];
				else
				{
					int ways=(foot[x]<(pts-st))+(foot[x]<=(pts-st));
					ans=ans*ways%MOD;st=pts;
				}
			}
			x=a[x];
		}
		if(fr)//circle of feet
		{
			int ways=(l1<(pts+fr-st))+(l1<=(pts+fr-st));
			ans=ans*ways%MOD;
		}
		else//just a circle
			cnt[pts]+=1;
	}
	for(int i=1;i<=n;++i)//dp,in order to calc each length of circles
	{
		if(!cnt[i])continue;
		f[0]=1;
		for(int j=1;j<=cnt[i];++j)
		{
			if(i>1&&(i&1))//odd circle
				f[j]=(f[j-1]<<1)%MOD;//two ways
			else//even circle
				f[j]=f[j-1];//only one way
			if(j>1)f[j]=(f[j]+1ll*f[j-2]*(j-1)%MOD*i%MOD)%MOD;
			//merge two circle in the same length
		}
		ans=1ll*ans*f[cnt[i]]%MOD;
	}
	printf("%d\n",ans);
	return 0;
}