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>
using namespace std;
const int N=1e5+100;
int p[N],vis[N],st[N],len[N],tot[N];
int head[N],nxt[N];
bool rt[N];
int f[N],g[N];
inline int dfs(int k) {
	int s=0;
	for (int i=head[k];i;i=nxt[i])
		if (!rt[i]) {
			if (s) puts("0"),exit(0);
			s=dfs(i)+1;
		}
	return s;
}
int main()
{
	const int mod=1e9+7;
	int n,i,k,t,s,cnt=0,top,ans=1,p2=0;
	bool is;
	for (i=1,cin>>n;i<=n;i++) cin>>p[i],nxt[i]=head[p[i]],head[p[i]]=i;
	for (i=1;i<=n;i++)
		if (!vis[i]) {
			++cnt;
			for (k=i;!vis[k];k=p[k])
				vis[k]=cnt;
			if (vis[k]!=cnt) continue;
			for (t=k,top=0;st[1]!=t;t=p[t]) rt[st[++top]=t]=true;
			reverse(st+1,st+1+top);
			is=false;
			for (k=1;k<=top;k++)
				is|=len[k]=dfs(st[k]);
			if (is) {
				for (k=1;k<=top;k++)
					if (len[k]) {
						for (t=k%top+1,s=1;!len[t];t=t%top+1,s++);
						if (s<len[k]) return puts("0"),0;
						if (s!=len[k]) p2++;
					}
			} else tot[top]++,p2+=top>1&&(top&1);
		}
	const int inv4=1LL*(mod+1)*(mod+1)/4%mod;
	for (i=1;i<=n;i++) {
		for (k=f[0]=f[1]=g[0]=g[1]=1;k<=tot[i];k++) {
			f[k+1]=(1LL*f[k-1]*k%mod*inv4%mod*i+f[k])%mod;
			g[k+1]=(1LL*g[k-1]*k%mod*i+g[k])%mod;
		}
		ans=1LL*ans*(i==1||i%2==0?g[tot[i]]:f[tot[i]])%mod;
	}
	while (p2--) (ans<<=1)%=mod;
	printf("%d\n",ans);
	return 0;
}