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 RI register int
#define g getchar()
using namespace std;
typedef long long ll;
const int mod=1e9+7,N=1e5+10;
void qr(int &x) {
	char c=g;x=0;
	while(!isdigit(c))c=g;
	while(isdigit(c))x=x*10+c-'0',c=g;
}
int n; ll ans;
int a[N],deg[N],vis[N],footL[N],sum[N],f[N];
bool cir[N];
int qm(int x) {return x>=mod?x-mod:x;}
void workcir(int x) {
	int now=0,fr=0,frL=0,ed=0;
	//now是当前环的长度，fr是第一个有脚点的位置,frL是位置对应的脚长,ed为上一个有脚点的位置。 
	while(cir[x]) {
		++now; cir[x]=0;
		if(footL[x]) {
			if(!fr) ed=fr=now,frL=footL[x];
			else {
				ans=ans*((footL[x]<now-ed)+(footL[x]<=now-ed))%mod;//脚的放法 
				ed=now;
			}
		}
		x=a[x];
	}
	if(!ed) ++sum[now];
	else ans=ans*((frL<now-ed+fr)+(frL<=now-ed+fr))%mod;
}
void work() {
	for(RI i=1;i<=n;i++) {//脚对环上交接点贡献 
		if(deg[i]) continue;
		int x=i,len=0; while(!cir[x])x=a[x],++len;
		footL[x]=len;//脚长 
	}
	ans=f[0]=1;
	for(RI i=1;i<=n;i++) if(cir[i]) workcir(i);//以环为基准计算基环内向树的情况 
	for(RI i=1;i<=n;i++) {//计算简单环 
		for(RI j=1;j<=sum[i];j++) {
			if(i>1&&(i&1)) f[j]=qm(f[j-1]<<1);
			else f[j]=f[j-1];
			if(j>1) f[j]=qm(f[j]+(ll)f[j-2]*(j-1)%mod*i%mod);
		}
		ans=ans*f[sum[i]]%mod;
	}
}
int main() {
	qr(n);
	for(RI i=1;i<=n;i++) qr(a[i]),++deg[a[i]];
	for(RI i=1;i<=n;i++) if(!vis[i]) {
		int x=i;while(!vis[x]) vis[x]=i,x=a[x];
		if(vis[x]!=i) continue;//脚 
		while(!cir[x]) cir[x]=1,x=a[x];//标记环上点 
	}
	for(RI i=1;i<=n;i++)
		if((cir[i]&&deg[i]>2)||(!cir[i]&&deg[i]>1)) return puts("0"),0;//开叉就不行 
	work(); printf("%lld\n",ans); return 0;
}