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>

const int MAXN = 100010;
const int mod = 1000000007;
typedef long long LL;
void bye() { std::cout << 0 << std::endl; exit(0); }
void reduce(int & x) { x += x >> 31 & mod; }
int mul(int a, int b) { return (LL) a * b % mod; }
int pow(int a, int b, int res = 1) {
	for (; b; b >>= 1, a = mul(a, a)) if (b & 1) res = mul(res, a);
	return res;
}
int A[MAXN], n, ind[MAXN], vis[MAXN];
int fac[MAXN], inv[MAXN], cnt[MAXN];
int C(int a, int b) { return (LL) fac[a] * inv[b] % mod * inv[a - b] % mod; }
std::vector<int> in[MAXN];
int ans = 1;
int main() {
	std::ios_base::sync_with_stdio(false), std::cin.tie(0);
	fac[0] = inv[0] = fac[1] = inv[1] = 1;
	for (int i = 2; i != MAXN; ++i) {
		fac[i] = mul(fac[i - 1], i);
		inv[i] = mul(inv[mod % i], mod - mod / i);
	}
	for (int i = 2; i != MAXN; ++i)
		inv[i] = mul(inv[i - 1], inv[i]);
	std::cin >> n;
	for (int i = 1; i <= n; ++i)
		std::cin >> A[i], ++ind[A[i]], in[A[i]].push_back(i);
	for (int i = 1; i <= n; ++i) if (ind[i] > 2) bye();
	for (int i = 1; i <= n; ++i) if (!vis[i] && !ind[i]) {
		static int li[MAXN], bak, cir[MAXN]; bak = 0;
		auto pre = [] (int x) { return x == 1 ? bak : x - 1; };
		int now = i;
		while (!vis[now]) {
			vis[now] = true;
			li[++bak] = now;
			now = A[now];
		}
		int at = std::find(li + 1, li + 1 + bak, now) - li;
		bak -= at - 1;
		for (int i = 1; i <= bak; ++i) li[i] = li[i + at - 1];
		for (int i = 1; i <= bak; ++i) {
			int u = li[i]; cir[i] = 0;
			for (auto t : in[u]) if (t != li[pre(i)]) {
				int now = t;
				while (true) {
					++cir[i];
					if (in[now].size() > 1) bye();
					if (in[now].empty()) break;
					now = in[now][0];
				}
			}
		}
		for (int i = 1; i <= bak; ++i) if (cir[i]) {
			int dis = 1, now = pre(i);
			while (!cir[now]) now = pre(now), ++dis;
			if (dis < cir[i]) bye();
			ans = mul(ans, 1 + (dis > cir[i]));
		}
	}
	for (int i = 1; i <= n; ++i) if (!vis[i]) {
		int now = A[i], l = 1; vis[i] = true;
		while (now != i) ++l, vis[now] = true, now = A[now];
		++cnt[l];
	}
	for (int i = 1; i <= n; ++i) {
		int t = 0;
		for (int j = 0; j <= cnt[i]; j += 2) {
			int t2 = (LL) C(cnt[i], j) * C(j, j / 2) % mod * fac[j / 2] % mod;
			t2 = pow(mul(i, mod + 1 >> 1), j / 2, t2);
			if (i > 1 && i % 2 == 1)
				t2 = pow(2, cnt[i] - j, t2);
			reduce(t += t2 - mod);
		}
		ans = mul(ans, t);
	}
	std::cout << ans << std::endl;
	return 0;
}