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>
#include<cstdlib>
#include<cassert>
typedef long long LL;
const int md=1e9+7,N=1e5+5;
int tot[N],n,a[N],deg[N],cnt,bel[N],L[N],ans=1,top[N];
bool vis[N],inc[N];
inline void fail(){puts("0");exit(0);}
inline void upd(int&a){a+=a>>31&md;}
int solve(int L){
	static int f[N];
	*f=1;
	for(int i=1;i<=tot[L];++i){
		if((L&1)&&(L>1))upd(f[i]=f[i-1]*2-md);else f[i]=f[i-1];
		if(i>1)f[i]=(f[i]+(i-1LL)*f[i-2]%md*L)%md;
	}
	return f[tot[L]];
}
int solve_tree(int id){
	int len=0,now=top[id],r=1;
	do{
		++len;
		now=a[now];
		if(L[now]){
			if(L[now]>len)return 0;
			if(L[now]<len)upd(r=r*2-md);
			len=0;
		}
	}while(now!=top[id]);
	return r;
}
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&&!vis[i]){
		int j;
		top[bel[i]=++cnt]=i;
		vis[i]=inc[i]=1;
		for(j=a[i];!vis[j];j=a[j])vis[j]=1,bel[j]=cnt,inc[j]=1;
		if(j!=i)fail();
	}else if(deg[i]>2)fail();
	for(int i=1;i<=n;++i)
	if(!vis[i]&&deg[i]==0){
		int x=i;
		while(!vis[x])x=a[x];
		if(!inc[x]||L[x])fail();
		int len=0;
		for(x=i;!inc[x];x=a[x])vis[x]=1,++len;
		L[x]=len;
	}
	for(int i=1;i<=n;++i)if(!vis[i]){
		assert(deg[i]==1),vis[i]=1;
		int x,len=1;
		for(x=a[i];!vis[x];x=a[x])vis[x]=1,++len;
		assert(x==i);
		++tot[len];
	}
	for(int i=1;i<=n;++i)if(tot[i])ans=(LL)ans*solve(i)%md;
	for(int i=1;i<=cnt;++i)
	ans=(LL)ans*solve_tree(i)%md;
	printf("%d\n",ans);
	return 0;
}