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<cstdlib>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define gt getchar()
#define ll long long
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
typedef std::pair<int,int> P;
#define mk std::make_pair
#define fr first
#define sc second
inline int in()
{
	int k=0;char ch=gt;bool p=1;
	while(ch<'-')ch=gt;if(ch=='-')ch=gt,p=0;
	while(ch>'-')k=k*10+ch-'0',ch=gt;
	return p?k:-k;
}
const int N=2e6+5,YL=1e9+7;
inline int MO(const int &x){return x>=YL?x-YL:x;}
inline void add(int &x,int y){if((x+=y)>=YL)x-=YL;}
int dep[N],a[N],bj[N],Q[N],len,top,b[N],tot,du[N],o[N],st[N],f[N],fa[N];
void check_circle()
{
	for(int i=1;i<=len;++i)if(du[Q[i]]^1)return;
	for(int i=1;i<=len;++i)bj[Q[i]]=3;b[++tot]=len;
}
void dfs(int u)
{
	bj[u]=1,o[u]=1;
	if(!bj[a[u]])return fa[a[u]]=u,dfs(a[u]),o[u]=0,void();
	if(o[a[u]])
	{
		len=0;
		for(int now=u;;now=fa[now])
		{Q[++len]=now,bj[now]=2;if(now==a[u])break;}
		check_circle();
	}
	o[u]=0;
}
void Dfs(int u){dep[a[u]]=dep[u]+1;if(bj[a[u]]>1)return;Dfs(a[u]);}
int solve(int x)
{
	int ans=1;Q[len=1]=x;
	for(int now=a[x];now^x;now=a[now])Q[++len]=now;
	std::reverse(Q+1,Q+len+1);
	for(int i=1;i<=len;++i)bj[Q[i]]=4,Q[len+i]=Q[i];
	for(int i=1,j;i<=len;++i)
		if(dep[Q[i]])
		{
			for(j=i+1;j<=(len<<1)&&!dep[Q[j]];++j);
			if(dep[Q[i]]>j-i)puts("0"),exit(0);
			if(dep[Q[i]]<j-i)add(ans,ans);i=j-1;
		}
	return ans;
}
int main()
{
	int n=in();for(int i=1;i<=n;++i)++du[a[i]=in()];
	for(int i=1;i<=n;++i)if(!du[i])dfs(i);
	for(int i=1;i<=n;++i)if(!bj[i])dfs(i);
	for(int i=1;i<=n;++i)
		if((bj[i]>1&&du[i]>2)||(bj[i]==1&&du[i]>1))return puts("0"),0;
	std::sort(b+1,b+tot+1);int ans=1;
	for(int i=1,j;i<=n;i=j)
	{
		for(j=i;j<=n&&b[i]==b[j];++j);f[i-1]=1;
		for(int k=i;k<j;++k)
		{
			f[k]=f[k-1];
			if(b[i]>1&&(b[i]&1))add(f[k],f[k-1]);
			if(k>i)f[k]=(1ll*f[k-2]*b[i]%YL*(k-i)+f[k])%YL;
		}
		ans=1ll*ans*f[j-1]%YL;
	}
	for(int i=1;i<=n;++i)if(bj[i]==1)bj[i]=0;
	for(int i=1;i<=n;++i)if(!du[i])Dfs(i);
	for(int i=1;i<=n;++i)if(bj[i]==2)ans=1ll*ans*solve(i)%YL;
	return printf("%d\n",ans),0;
}