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;
typedef long long LL;
typedef double db;
#define go(u) for(int i = head[u], v = e[i].to; i; i=e[i].lst, v=e[i].to)
#define rep(i, a, b) for(int i = a; i <= b; ++i)
#define pb push_back
#define re(x) memset(x, 0, sizeof x)
inline int gi() {
    int x = 0,f = 1;
    char ch = getchar();
    while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar();}
    while(isdigit(ch)) { x = (x << 3) + (x << 1) + ch - 48; ch = getchar();}
    return x * f;
}
template <typename T> inline bool Max(T &a, T b){return a < b ? a = b, 1 : 0;}
template <typename T> inline bool Min(T &a, T b){return a > b ? a = b, 1 : 0;}
const int N = 1e5 + 7, mod = 1e9 + 7;
int n, sz, tsum;
int vis[N], cir[N], fa[N], oncir[N], val[N], cnt[N], du[N];
LL ans = 1, f[N];
vector<int>G[N];
void tarjan(int u) {
	++tsum;
	vis[u] = 1;
	for(auto v:G[u]) if(!vis[v]) {
		fa[v] = u;
		tarjan(v);
	}else {
		cir[sz++] = u;
		for(int x = u; x ^ v; x = fa[x]) {
			cir[sz++] = fa[x];
		}
	}
}
int dfs(int u) {
	int cnt = 0;
	for(auto v:G[u]) if(!oncir[v]) ++cnt;
	if(cnt >= 2) puts("0"), exit(0);
	for(auto v:G[u]) if(!oncir[v]) {
		return dfs(v) + 1;
	}
	return 0;
}
int calc(int a, int b) {
	if(a < b) return 2;
	return a == b;
}
void solve() {
	rep(i, 0, sz - 1) val[i] = dfs(cir[i]);
	
	LL tot = 1; int L = -1, R = -1;
	for(int i = 0; i < sz; ++i) if(val[i]) { L = i; break;}
	for(int i = sz - 1; i >= 0; --i) if(val[i]) { R = i; break;}
	tot = tot * calc(val[L], sz - 1 - R + L + 1) % mod;
	for(int i = L + 1; i < sz; ++i) if(val[i]) {
		tot = tot * calc(val[i], i - L) % mod;
		L = i;
	}
	ans = ans * tot % mod;
}
int gg(int a) {
	if(a == 1 || a % 2 == 0) return 1;
	return 2;
}
vector<int>H[N];
int main() {
#ifdef fwat
	freopen("data.in", "r", stdin);
#endif
	n = gi();
	rep(i, 1, n) oncir[i] = 1;
	rep(i, 1, n) {
		int a = gi();
		G[a].pb(i);
		H[i].pb(a);
		++du[a];
	}
	queue<int>Q;
	rep(i, 1, n) if(!du[i]) Q.push(i);
	while(!Q.empty()) {
		int u = Q.front();Q.pop();
		oncir[u] = 0;
		for(auto v:H[u]) if(--du[v] == 0) Q.push(v);
	}
	rep(i, 1, n) if(oncir[i] && !vis[i]) {
		tsum = sz = 0;
		tarjan(i);
		if(sz == tsum)
			++cnt[tsum];
		else
			solve();
	}
	rep(len, 1, n) {
		fill(f, f + cnt[len] + 1, 0);
		f[0] = 1, f[1] = gg(len);
		rep(i, 2, cnt[len]) f[i] = (f[i - 1] * gg(len) + (i - 1ll) * len % mod * f[i - 2]) % mod;
		ans = ans * f[cnt[len]] % mod;
	}
	printf("%lld\n", ans);
	return 0;
}