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 <queue>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define N 100100
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define rep(x, a, b) for(int x=a; x<=b; x++)
#define drp(x, a, b) for(int x=a; x>=b; x--)
int deg[N], d[N], n, vis[N], a[N], tot, num[N], l[N], ans=1, fac[N], inv[N];
vector<pair<int, int> > fu;
queue<int> q;
int power(int a, int k){
	int ret=1;
	while(k)
	{
		if(k&1) ret=1ll*ret*a%mod;
		a=1ll*a*a%mod; k>>=1;
	}
	return ret;
}
int C(int n, int m){
	return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int pr(int n){
	return 1ll*fac[2*n]*inv[n]%mod*power((mod+1)>>1, n)%mod;
}
void init(){
	fac[0]=1;
	rep(i, 1, n) fac[i]=1ll*fac[i-1]*i%mod;
	inv[n]=power(fac[n], mod-2);
	drp(i, n, 1) inv[i-1]=1ll*inv[i]*i%mod;
}

int st[N<<1];
void renew(int &x, const int y){
	x += y;
	if(x < 0) x += mod;
	if(x >= mod) x -= mod;
}
int getdp(){
	int fr = 0;
	rep(i, 1, tot) st[i + tot] = st[i];
	rep(i, 1, tot) if(l[st[i]]){
		fr = i;
		break;
	}
	reverse(st + fr + 1, st + fr + tot);
	int a = fr + l[st[fr]] - 1, b = a + 1, c = 1;
	rep(i, fr + 1, fr + tot - 1)if(l[st[i]]){
		int na = i + l[st[i]] - 1, nb = na + 1, cc = 0;
		if(a < i) renew(cc, c);
		if(b < i) renew(cc, c);
		a = na;
		b = nb;
		c = cc;
	}
	int ans = 0;
	if(a < fr + tot) renew(ans, c);
	if(b < fr + tot) renew(ans, c);
	return ans;
}

int main(){
	scanf("%d", &n);
	init();
	rep(i, 1, n)
	{
		scanf("%d", a+i);
		deg[a[i]]++;
	}
	rep(i, 1, n) if(deg[i]>2) return puts("0"), 0;
	rep(i, 1, n) d[i]=deg[i];
	rep(i, 1, n) if(!d[i]) q.push(i);
	while(!q.empty())
	{
		int u=q.front(); q.pop();
		vis[u]=1;
		if(--d[a[u]]==0) q.push(a[u]);
	}
	rep(i, 1, n) if(vis[i] && deg[i]>1) return puts("0"), 0;
	rep(i, 1, n) if(vis[i] && !deg[i])
	{
		int x=i, cnt=0;
		for(; vis[x]; x=a[x]) cnt++;
		l[x]=cnt;
	}
	rep(i, 1, n) if(!vis[i])
	{
		int x=i, fl=0, ass=1; tot=0;
		for(; !vis[x]; x=a[x]) st[++tot]=x, fl|=bool(l[x]), vis[x]=1;
		if(!fl) num[tot]++;
		else
		{
			fu.clear();
			//if(l[i]) fu.pb(mp(l[i], 0));
			//for(int p=1, x=a[i]; x!=i; x=a[x]) if(l[x]) fu.pb(mp(l[x], p));
			rep(p, 1, tot) if(l[st[p]]) fu.pb(mp(l[st[p]], p));
			fu.pb(mp(fu[0].fi, fu[0].se+tot));
			int sz=fu.size();
			rep(j, 1, sz-1)
			{
				if(fu[j].fi>fu[j].se-fu[j-1].se) ass=0;
				if(fu[j].fi<fu[j].se-fu[j-1].se) ass=2ll*ass%mod;
			}
//			ass=getdp();
		}
		ans=1ll*ans*ass%mod;
	}
	rep(i, 1, n) if(num[i])
	{
		int m=num[i], ass=0;
		rep(j, 0, m/2)
		{
			int tmp=1ll*C(m, 2*j)*pr(j)%mod*power(i, j)%mod;
			if(i>1 && (i&1)) tmp=1ll*tmp*power(2, m-2*j)%mod;
			ass=(ass+tmp)%mod;
		}
		ans=1ll*ans*ass%mod;
	}
	printf("%d\n", ans);
}