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:
// Next or Nextnext
// * frank_c1
// * 2017 / 09 / 29

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

LL pow_mod(LL b, LL p, LL k) {
	LL ret = 1;
	for (; p; p >>= 1) {
		if (p & 1) ret = ret * b % k;
		b = b * b % k; 
	} return ret;
}

const int maxn = (int)(1e5) + 5;
const int mo = (int)(1e9) + 7;
int a[maxn], in[maxn], w[maxn], cnt[maxn], vi[maxn], s[maxn];
int q[maxn], l = 1, r, len;
LL fac[maxn], ivf[maxn], pw[maxn];

inline LL C(int n, int m) {
	if (m < 0 || n - m < 0) return 0;
	return (fac[n] * ivf[m] % mo) * ivf[n - m] % mo;
}

inline LL F(int n, int m) {
	return (C(n, m << 1) * C(m << 1, m) % mo) * (pow_mod(pw[m], mo - 2, mo) * fac[m] % mo) % mo;
}

int calc() {
	LL now = 1;
	for (int i = 1; i <= len; ++i) if (cnt[w[i]]) {
		int ps = i, v = 0;
		do {
			++v; --ps; if (ps < 1) ps = len;
		} while (!cnt[w[ps]]);
		if (v < cnt[w[i]]) return 0;
		if (v > cnt[w[i]]) now = now * 2 % mo;
	} return now;
}

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), ++in[a[i]];
	fac[0] = ivf[0] = pw[0] = 1;
	for (int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % mo, pw[i] = pw[i - 1] * 2 % mo;
	ivf[n] = pow_mod(fac[n], mo - 2, mo);
	for (int i = n - 1; i >= 1; --i) ivf[i] = ivf[i + 1] * (i + 1) % mo;
	memcpy(w, in, sizeof(in));
	for (int i = 1; i <= n; ++i) if (!in[i]) q[++r] = i;
	for (; l <= r; ) {
		int x = q[l++];
		if (!(--in[a[x]])) q[++r] = a[x]; cnt[a[x]] = cnt[x] + 1;
	}
	for (int i = 1; i <= n; ++i) if (w[i] - in[i] > 1) return printf("0\n"), 0;
	LL ret = 1;
	for (int i = 1; i <= n; ++i) if (in[i] && !vi[i]) {
		int x = i, c = 0; len = 0;
		while (!vi[x]) {
			w[++len] = x; vi[x] = 1; if (cnt[x]) c = 1; x = a[x];
		}
		if (!c) ++s[len]; else ret = ret * calc() % mo;
	} 
	for (int i = 1; i <= n; ++i) if (s[i]) {
		LL tmp = 0, ww = 1; 
		for (int j = 0; j <= (s[i] >> 1); ++j) {
			LL buf = 1; 
			(buf *= (F(s[i], j) * ww % mo)) %= mo;
			if ((i & 1) && i > 1) (buf *= pw[s[i] - (j << 1)]) %= mo; 
			ww = ww * i % mo; (tmp += buf) %= mo; 
		} (ret *= tmp) %= mo;
	} 
	return printf("%lld\n", ret), 0;
}