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 <bits/stdc++.h>
#define pb push_back
#define cmin(a,b) (a>b?a=b:a)
#define cmax(a,b) (a<b?a=b:a)
#define mem(a,k) memset(a,k,sizeof(a))
#define lop(i,s,t) for(int i=s;i<(t);++i)
#define rep(i,s,t) for(int i=s;i<=(t);++i)
#define dec(i,s,t) for(int i=s;i>=(t);--i)
#define fore(i,v) for(int i=g[v],d=es[i].d;i;i=es[i].nxt,d=es[i].d)
using namespace std;

#define Pr(f,...) //fprintf(stderr,f,##__VA_ARGS__),fflush(stderr)

typedef long long ll;

template<typename T>
void read(T &x){
	x=0; 
	char c;
	for(c=getchar();!isdigit(c);c=getchar()); 
	for(;isdigit(c);c=getchar())x=x*10+c-'0'; 
}

const int N=1e5+50,P=1e9+7;

int mul(int a,int b){ return 1ll*a*b%P; }
int add(int a,int b){ a+=b; return a>=P?a-P:a; }
int sub(int a,int b){ a-=b; return a<0?a+P:a; }

vector<int> cir[N];
int fail,len[N],vis[N],f[N];
int n,to[N],deg[N],blg[N],m,cnt[N]; 

void dfs(int v){
	vis[v]=2; 
	if(vis[to[v]]==2){
		++m;
		for(int x=to[v];;x=to[x]){
			blg[x]=m;
			cir[m].pb(x);
			if(x==v)break;
		}
	}else if(!vis[to[v]]){
		dfs(to[v]); 
	}
	vis[v]=1;
}

int process(vector<int> &c){
	vector<int> b;
	lop(i,0,(int)c.size()){
		if(len[c[i]])b.pb(i); 
		if(len[c[i]])Pr("len[%d]=%d\n",c[i],len[c[i]]); 
	}
	int res=1,nb=b.size(),nc=c.size();
	if(b.empty()){
		++cnt[c.size()];
		return res;
	}
	Pr("process : "); for(int x:c)Pr("%d ",x); Pr("\n"); 

	lop(i,0,(int)b.size()){
		int p=(i-1+nb)%nb,d=(b[i]-b[p]+nc)%nc,l=len[c[b[i]]];
		if(d==0)d=nc;
		Pr("i=%d,b[i]=%d,c[b[i]]=%d,d=%d,l=%d\n",i,b[i],c[b[i]],d,l); 
		res=mul(res,(d>=l)+(d>l));
	}
	return res;
}

int main(int argc,char *argv[]){
#ifdef CURIOUSCAT
	freopen("dat.in","r",stdin);
	freopen("my.out","w",stdout);
#endif
	read(n); 
	rep(i,1,n){
		read(to[i]); 
		++deg[to[i]];
		Pr("to[%d]=%d\n",i,to[i]); 
	}	
	rep(i,1,n){
		if(!vis[i]){
			dfs(i); 
		}
	}
	rep(i,1,n){
		if(blg[i]&&deg[i]>2)fail=true;
		if(!blg[i]&&deg[i]>1)fail=true;
	}
	rep(i,1,n){
		if(deg[i])continue;
		int x,c=0; 
		for(x=i;!blg[x];x=to[x])++c;
		len[x]=c;
	}
	int ans=1;
	rep(k,1,m){
		ans=mul(ans,process(cir[k])); 
	}
	if(!ans)fail=true;
	Pr("ans=%d\n",ans); 
	rep(l,1,n){
		Pr("f[%d]=%d\n",l,f[l]); 
		int w=(l&1)+(l>1); 
		f[0]=1;
		rep(i,1,cnt[l]){
			f[i]=mul(f[i-1],w); 	
			if(i>1)f[i]=add(f[i],mul(f[i-2],mul(i-1,l)));
		}
		ans=mul(ans,f[cnt[l]]); 
	}
	Pr("fail=%d\n",(int)fail); 
	printf("%d\n", fail?0:ans);
	return 0;
}