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>
using namespace std;
const int mxn=1000010,md=1000000007;
int power(int x,int p,int num=1){
	for (;p;p>>=1,x=1ll*x*x%md)
		if (p&1) num=1ll*num*x%md;
	return num;
}
int ans,c[mxn],stk[mxn],tp,son[mxn],vis[mxn],cnt[mxn];
int solve_tr(){
	int lst=0;
	for (int i=1;i<=tp;++i) cnt[i]=0;
	for (int i=1;i<=tp;++i)
		for (int x=son[stk[i]];x;++cnt[i],vis[x]=1,x=son[x]);
	for (int i=1;i<=tp;++i)
		if (cnt[i]) {lst=i;break;}
	if (!lst) return ++c[tp],1;
	int ret=1;
	for (int i=tp;i;++lst,--i)
		if (cnt[i]){
			if (lst>cnt[i]) ret=ret*2%md;
			if (lst<cnt[i]) return 0;
			lst=0;
		}
	return ret;
}
int f[mxn],pw[mxn],fct[mxn],ifc[mxn];
int cal(int x){
	return (x-1ll)*x/2%md;
}
int solve_lp(int n,int k){
	f[0]=1;
	bool flg=((k&1)&&k>1);
	int ret=pw[flg*n];
	for (int i=1;i<<1<=n;++i){
		f[i]=1ll*f[i-1]*cal(n-(i<<1)+2)%md*k%md;
		ret=(ret+1ll*f[i]*ifc[i]%md*pw[flg*(n-(i<<1))])%md;
	}
	return ret;
}
void init(int n){
	pw[0]=1;
	for (int i=1;i<=n;++i) pw[i]=pw[i-1]*2%md;
	fct[0]=ifc[0]=1;
	for (int i=1;i<=n;++i) fct[i]=1ll*fct[i-1]*i%md;
	ifc[n]=power(fct[n],md-2);
	for (int i=n-1;i;--i) ifc[i]=(i+1ll)*ifc[i+1]%md;
}
int n,fa[mxn],stkk[mxn],tpp,tag[mxn],exist[mxn];
bool init2(){
	for (int i=1;i<=n;++i)
		if (!vis[i]){
			tpp=0;
			for (int x=i;x;x=fa[x])
				if (vis[x]){
					if (!exist[x]) break;
					for (;stkk[tpp+1]!=x;tag[stkk[tpp]]=1,exist[stkk[tpp--]]=0);
					break;
				}
				else vis[x]=exist[x]=1,stkk[++tpp]=x;
			for (;tpp;exist[stkk[tpp--]]=0);
		}
	memset(vis,0,sizeof(vis));
	for (int i=1;i<=n;++i)
		if (!tag[i]){
			if (son[fa[i]]) return 0;
			son[fa[i]]=i;
		}
	return 1;
}
int main()
{
	scanf("%d",&n);
	init(n);
	for (int i=1;i<=n;++i) scanf("%d",&fa[i]);
	if (!init2()) return puts("0"),0;
	int ans=1;
	for (int i=1;i<=n;++i)
		if (tag[i]&&!vis[i]){
			tp=tpp=0;
			for (int x=i;x;x=fa[x])
				if (vis[x]){
					for (;stkk[tpp+1]!=x;stk[++tp]=stkk[tpp--]);
					break;
				}
				else vis[x]=1,stkk[++tpp]=x;
			ans=1ll*ans*solve_tr()%md;
		}
	for (int i=1;i<=n;++i)
		ans=1ll*ans*solve_lp(c[i],i)%md;
	printf("%d\n",ans);
	return 0;
}