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 rep(i,x,y) for (int i=(x);i<=(y);i++)
#define ll long long

using namespace std;

const int N=1e5+10,mod=1e9+7;
int n,cnt,head[N],vis[N],a[N];
int tot,cir_tot,q[N],fa[N],dep[N],mk[N],len[N];
int sum[N],ans,f[N];
struct edge{int to,nxt;}e[N<<1];

void adde(int x,int y){
	e[++cnt].to=y; e[cnt].nxt=head[x]; head[x]=cnt;
}

void dfs(int u,int par){
	vis[u]=1; tot++;
	for (int i=head[u],v;i;i=e[i].nxt)
		if ((i^1)!=par){
			v=e[i].to;
			if (!vis[v]) fa[v]=u,dep[v]=dep[u]+1,dfs(v,i);
			else if (dep[v]<=dep[u]){
				for (int i=u;i!=v;i=fa[i]) q[++cir_tot]=i,mk[i]=1;
				q[++cir_tot]=v,mk[v]=1;
			}
		}
}

int tmp;
void dfs1(int u,int par){
	if (par) tmp++;
	int son=0;
	for (int i=head[u],v;i;i=e[i].nxt)
		if (v=e[i].to,v!=par&&!mk[v]) dfs1(v,u),son++;
	if (son>1){puts("0"); exit(0);}
}

int main(){
	scanf("%d",&n);
	cnt=1;
	rep (i,1,n) scanf("%d",&a[i]),adde(a[i],i),adde(i,a[i]);
	ans=1;
	rep (i,1,n) if (!vis[i]){
		tot=cir_tot=0,dfs(i,-1);
		if (cir_tot==2&&q[1]==q[2]) cir_tot--;
		if (tot==cir_tot) sum[tot]++;
		else{
			if (a[q[1]]!=q[2]) reverse(q+1,q+1+cir_tot);
			int st=1;
			rep (j,1,cir_tot){
				tmp=0,dfs1(q[j],0),len[j]=tmp;
				if (tmp) st=j;
			}
			int len_2=0;
			for (int j=st%cir_tot+1;;j=j%cir_tot+1){
				len_2++;
				if (len[j]){
					ans=(ll)ans*((len[j]<=len_2)+(len[j]<len_2))%mod;
					len_2=0;
				}
				if (j==st) break;
			}
		}
	}
	rep (i,1,n){
		if (!sum[i]) continue;
		f[0]=1;
		rep (j,1,sum[i]){
			f[j]=f[j-1];
			if (i>1&&(i&1)) f[j]=(f[j]+f[j-1])%mod;
			if (j>1) f[j]=(f[j]+(ll)f[j-2]*(j-1)%mod*i%mod)%mod;
		}
		ans=(ll)ans*f[sum[i]]%mod;
	}
	printf("%d\n",ans);
	return 0;
}