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 <cstring>
#include <algorithm>
#define MAXN 200010
#define LL long long
using namespace std;

const LL P=1000000007;

LL getPow(LL x,LL y){
	LL res=1;
	while(y){
		if(y&1) res=res*x%P;
		x=x*x%P;
		y>>=1;
	}
	return res;
}

struct edge{
	int to,next;
	edge(int _to=0,int _next=0):to(_to),next(_next){}
}e[MAXN];

int n;
int g[MAXN],nume;
int p[MAXN];
bool visit0[MAXN],visit[MAXN];
int b[MAXN],l[MAXN],sl[MAXN],numb;
int cnt[MAXN];
LL f[MAXN],fac[MAXN],invfac[MAXN];
LL ans=1;

void addEdge(int u,int v){
	e[nume]=edge(v,g[u]);
	g[u]=nume++;
}

int dfs(int x){
	visit[x]=1;
	int numch=0;
	int res=0;
	for(int i=g[x];~i;i=e[i].next)
		if(!visit[e[i].to]){
			numch++;
			res=dfs(e[i].to)+1;
		}
	if(numch>=2) ans=0;
	return res;
}

void gao(int x){
	numb=0;
	while(!visit[x]){
		visit[x]=1;
		b[++numb]=x;
		x=p[x];
	}
	int pos=0;
	for(int i=1;i<=numb;i++){
		l[i]=dfs(b[i]);
		if(l[i]) pos=i;
	}
	if(!pos){
		cnt[numb]++;
		return;
	}
	for(int i=1;i<=numb;i++){
		b[i+numb]=b[i];
		l[i+numb]=l[i];
		b[i]=b[i+pos-1];
		l[i]=l[i+pos-1];
	}
	for(int i=1;i<=numb;i++) sl[i]=sl[i-1]+l[i];
	LL res1=0,res2=0;
	if(sl[numb]-sl[numb-(l[1]-1)]==0){
		res1=1;
		for(int i=2;i<=numb;i++){
			if(!l[i]) continue;
			LL temp=0;
			if(sl[i-1]-sl[max(0,i-l[i])]==0) temp++;
			if(sl[i-1]-sl[max(0,i-l[i]-1)]==0) temp++;
			res1=res1*temp%P;
		}
	}
	if(sl[numb]-sl[numb-l[1]]==0){
		res2=1;
		for(int i=2;i<=numb;i++){
			if(!l[i]) continue;
			LL temp=0;
			if(sl[i-1]-sl[max(0,i-l[i])]==0) temp++;
			if(sl[i-1]-sl[max(0,i-l[i]-1)]==0) temp++;
			res2=res2*temp%P;
		}
	}
	ans=ans*(res1+res2)%P;
}

void init(){
	f[0]=1;
	for(int i=2;i<=n;i++) f[i]=f[i-2]*(i-1)%P;
	fac[0]=1;
	for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%P;
	invfac[n]=getPow(fac[n],P-2);
	for(int i=n-1;i>=0;i--) invfac[i]=invfac[i+1]*(i+1)%P;
}

LL getC(int x,int y){
	return fac[x]*invfac[y]%P*invfac[x-y]%P;
}

int main(){
#ifdef DEBUG
	freopen("E.in","r",stdin);
#endif
	memset(g,-1,sizeof g);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",p+i);
		addEdge(p[i],i);
	}
	for(int i=1;i<=n;i++)
		if(!visit[i]){
			int x=i;
			for(;!visit0[x];x=p[x]) visit0[x]=1;
			gao(x);
		}
	init();
	for(int i=1;i<=n;i++)
		if(cnt[i]){
			LL res=0;
			for(int j=0;j<=cnt[i];j+=2)
				if(i>=3 && (i&1)) res=(res+getC(cnt[i],j)*f[j]%P*getPow(i,j/2)%P*getPow(2,cnt[i]-j))%P;
				else res=(res+getC(cnt[i],j)*f[j]%P*getPow(i,j/2))%P;
			ans=ans*res%P%P;
		}
	printf("%lld\n",ans);
	return 0;
}