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 <stdio.h>
#include <iostream>
#include <algorithm>
#include <memory.h>

using namespace std;
typedef long long LL;
const int maxn = 200005;
const int mod = 1e9+7;

bool vis[maxn],ins[maxn];int n,a[maxn],deg[maxn];int ans=1;
bool onring[maxn];int stk[maxn],top,len[maxn],cnt[maxn];
int fac[maxn],inc[maxn],pw[maxn],ffac[maxn];

int fpm(LL p,int k) {
	LL res=1ll;
	while (k) {
		if (k&1) (res*=p)%=mod;
		(p*=p)%=mod;k>>=1;
	}
	return res;
}
LL comb(int n,int m) {
	return (LL)fac[n]*inc[m]%mod*(LL)inc[n-m]%mod;
}

void dfs(int u)
{
	stk[++top]=u;ins[u]=vis[u]=true;
	if (ins[a[u]]) {
		onring[a[u]]=true;
		for (int j=top;stk[j]!=a[u];j--)
			onring[stk[j]]=true;
	}
	if (!vis[a[u]]) dfs(a[u]);
	top--;ins[u]=false;
}
void dfs2(int u,int dis)
{
	if (onring[u]) len[u]=dis;
	else dfs2(a[u],dis+1);
}
void calc(int u)
{
	vis[u]=true;
	for (int v=a[u];v!=u;v=a[v]) vis[v]=true;
	if (!len[u]) {
		int v=a[u],dis=1;
		while (v!=u&&!len[v]) {v=a[v],++dis;}
		if (v==u) {cnt[dis]++;return ;}
		u=v;
	}
	for (int co=0,i=u,j;!co||i!=u;co++,i=j)
	{
		int dis=1;j=a[i];while (!len[j]) j=a[j],++dis;
		if (dis<len[j]) {puts("0");exit(0);}
		if (dis>len[j]) (ans<<=1)%=mod;
	}
}
int main()
{
	#ifdef Amberframe
		freopen("agc008e.in","r",stdin);
		freopen("agc008e.out","w",stdout);
	#endif
	scanf("%d",&n);fac[0]=inc[0]=ffac[0]=pw[0]=1;
	for (int i=1;i<=n;i++) scanf("%d",&a[i]),deg[a[i]]++;

	for (int i=1;i<=n;i++) if (!vis[i]) dfs(i);
	for (int i=1;i<=n;i++) if (onring[i]+1<deg[i]) {puts("0");return 0;}
	for (int i=1;i<=n;i++) if (!deg[i]) dfs2(i,0);
	memset(vis,0,sizeof vis);
	for (int i=1;i<=n;i++) if (onring[i]&&!vis[i]) calc(i);
	
	for (int i=1;i<=n;i++) ffac[i]=(LL)(2*i-1)*ffac[i-1]%mod;
	for (int i=1;i<=n;i++) fac[i]=(LL)fac[i-1]*i%mod;
	inc[n]=fpm(fac[n],mod-2);
	for (int i=n;i>=2;i--) inc[i-1]=(LL)inc[i]*i%mod;
	for (int i=1;i<=n;i++) pw[i]=(LL)pw[i-1]*2ll%mod;
	
	for (int i=1;i<=n;i++)
	if (i&1) {
		int o=cnt[i],res=0,lx=1;
		for (int x=0;x*2<=o;x++,lx=(LL)lx*i%mod)
			res=(res+(LL)comb(o,x*2)*ffac[x]%mod*(LL)lx%mod*(i>1?pw[o-2*x]:1))%mod;
		ans=(LL)ans*res%mod;
	}
	else {
		int o=cnt[i],res=0,lx=1;
		for (int x=0;x*2<=o;x++,lx=(LL)lx*i%mod)
			res=(res+(LL)comb(o,x*2)*ffac[x]%mod*(LL)lx)%mod;
		ans=(LL)ans*res%mod;
	}
	printf("%d",ans<0?ans+mod:ans);
	return 0;
}