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 <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cassert>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// head

const int N=101000;
VI vp,e[N],s[N];
int vis[N],cyc[N],inc[N],a[N],pre[N],n,cycnt[N];
ll ret,f[N];
void dfs(int u) {
	vp.pb(u); vis[u]=1;
	for (auto v:e[u]) if (!vis[v]) dfs(v);
}
bool check(VI &v) {
	int c=v[0];
	for (auto u:v) vis[u]=0;
	int m=0;
	while (1) {
		vis[c]=1;
		c=a[c];
		if (vis[c]==1) break;
	}
	int d=c;
	while (1) {
		cyc[m++]=c;
		inc[c]=1;
		c=a[c];
		if (c==d) break;
	}
	for (auto u:v) vis[u]=1;
	if (m==SZ(v)) {
		cycnt[m]++;
		return 1;
	}
	for (auto u:v) {
		if (SZ(s[u])>2) return 0;
		if (SZ(s[u])==2&&!inc[u]) return 0;
	}
	rep(i,0,m) pre[cyc[i]]=cyc[(i+m-1)%m];
	rep(i,0,m) {
		int u=cyc[i];
		if (SZ(s[u])==1) continue;
		int nbr=(s[u][0]==pre[u])?s[u][1]:s[u][0];
		VI chain; chain.pb(nbr);
		while (1) {
			if (SZ(s[nbr])==0) break;
			assert(SZ(s[nbr])==1);
			nbr=s[nbr][0];
			chain.pb(nbr);
		}
		bool v1=1,v2=1; nbr=pre[u];
		rep(j,0,SZ(chain)-1) {
			if (SZ(s[nbr])==2) v1=0,v2=0;
			nbr=pre[nbr];
		}
		if (SZ(s[nbr])==2) v2=0;
		if (v1==0) return 0;
		if (v2==1) ret=ret*2%mod;
	}
	return 1;
}

ll fac[N],fnv[N];
ll comb(int x,int y) {
	return fac[x]*fnv[y]%mod*fnv[x-y]%mod;
}
int main() {
	ret=1;
	scanf("%d",&n);
	rep(i,1,n+1) scanf("%d",a+i);
	fac[0]=fnv[0]=1;
	rep(i,1,n+1) fac[i]=fac[i-1]*i%mod,fnv[i]=powmod(fac[i],mod-2);
	rep(i,1,n+1) {
		e[i].pb(a[i]); e[a[i]].pb(i);
		s[a[i]].pb(i);
	}
	rep(i,1,n+1) if (!vis[i]) {
		vp.clear();
		dfs(i);
		if (!check(vp)) {
			puts("0");
			return 0;
		}
	}
	// deal with cycle
	f[0]=1;
	rep(i,1,n+1) f[i]=f[i-1]*(2*i-1)%mod;
	rep(i,1,n+1) if (cycnt[i]!=0) {
		ll r=0;
		for (int j=0;2*j<=cycnt[i];j++) {
			r=(r+comb(cycnt[i],2*j)*f[j]%mod*powmod(i,j)%mod*powmod((i%2==1&&i!=1)?2:1,cycnt[i]-2*j))%mod;
		}
		ret=ret*r%mod;
	}
	printf("%lld\n",ret);
}