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>
#define ref(i,x,y)for(int i=x;i<=y;++i)
const int N=100005,mod=1e9+7;
void print(int x){printf("%d\n",x);exit(0);}
int n,m,l,res,a[N],cnt,head[N],h[N],w[N*2],p[N],f[N];bool b[N],vis[N];
struct edge{int to,nxt;}e[N];
void add(int x,int y){e[++cnt]=(edge){y,head[x]};head[x]=cnt;}
int dfs(int f,int x){
	vis[x]=1;
	int Y=0,t=0;
	for(int i=head[x];i;i=e[i].nxt){
		int y=e[i].to;if(y!=f)Y=y,t++;
	}
	if(t>1)return 0;
	if(t==0)return 1;
	int s=dfs(x,Y);if(s)++s;
	return s;
}
int main(){
	scanf("%d",&n);
	ref(i,1,n)scanf("%d",&a[i]),add(a[i],i);
	res=1;
	ref(i,1,n)if(!vis[i]){
		m=l=0;
		for(int x=i;;b[x]=1,x=a[x]){
			h[++m]=x;if(b[x])break;
		}
		bool fg=0;
		for(int x=m;x==m||h[x]!=h[m];x--){
			w[++l]=dfs(h[x-1],h[x]);
			if(!w[l])print(0);w[l]--;
		}
		ref(i,1,l)w[i+l]=w[i];
		ref(i,1,l)if(w[i]){
			fg=1;int tt=0;
			ref(j,i+1,2*l)if(!w[j])tt++;else break;
			if(tt<w[i]-1)print(0);
			if(tt>w[i]-1)(res*=2)%=mod;
		}
		if(!fg)p[l]++;
	}
	ref(i,1,n)if(p[i]){
		f[0]=1;if((i&1)&&i>1)f[1]=2;else f[1]=1;
		if((i&1)&&i>1) ref(j,2,p[i])f[j]=(1LL*f[j-2]*(j-1)%mod*i+2*f[j-1])%mod;
		else ref(j,2,p[i])f[j]=(1LL*f[j-2]*(j-1)%mod*i+f[j-1])%mod;
		res=1LL*res*f[p[i]]%mod;
	}
	print(res);
}