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;
const int N = 1e5 + 5, MOD = 1e9 + 7;
int a[N], vis[N], chain[N], in[N], len[N];
bool in_circle[N];
int main() {
	int n;
	scanf("%d", &n);
	bool flag = 0;
	for (int i = 1; i <= n; ++ i) {
		scanf("%d", &a[i]);
		in[a[i]] ++;
		if (in[a[i]] >= 3) flag = 1;
	}
	if (flag) return 0 * puts("0");
	vector<vector<int>> circles;
	int xxx = 0;
	for (int i = 1; i <= n; ++ i) {
		if (vis[i]) continue;
		++ xxx;
		vis[i] = xxx;
		vector<int> st;
		st.push_back(i);
		int j = a[i];
		while (!vis[j]) {
			st.push_back(j);
			vis[j] = xxx;
			j = a[j];
		}
		if (vis[j] < xxx) continue;
		int end = j;
		vector<int> t;
		while (t.empty() || t.back() != end) {
			t.push_back(st.back());
			st.pop_back();
		}
		for (int x : t) in_circle[x] = 1;
		circles.push_back(t);
	}
	for (int i = 1; i <= n; ++ i) {
		if (in_circle[i]) continue;
		if (in[i] == 2) flag = 1;
		if (in[i]) continue;
		int cnt = 0, j = i;
		while (!in_circle[j]) {
			j = a[j];
			cnt ++;
		}
		chain[j] = cnt;
	}
	if (flag) return 0 * puts("0");
	unordered_map<int, int> nofeet;
	vector<vector<int>> feet;
	for (auto &t : circles) {
		bool has = 0;
		for (int x : t) {
			if (chain[x]) has = 1;
		}
		if (has) feet.push_back(t); else nofeet[(int) t.size()] ++;
	}
	int ans = 1;
	for (auto xy : nofeet) {
		int n = xy.first, cnt = xy.second;
		//printf("no feet : n=%d cnt=%d\n", n, cnt);
		static int dp[N];
		dp[0] = 1;
		for (int i = 1; i <= cnt; ++ i) {
			dp[i] = 1LL * dp[i - 1] * ((n & 1) && n > 1 ? 2 : 1) % MOD;
			if (i > 1) (dp[i] += 1LL * (i - 1) * n % MOD * dp[i - 2] % MOD) %= MOD;
		}
		ans = 1LL * ans * cnt[dp] % MOD;
	}
	for (auto &t : feet) {
		int n = (int) t.size(), st;
		for (int i = 0; i < n; ++ i) if (chain[t[i]]) {
			st = i;
			break;
		}
		int res = 0;
		for (int i = 0; i < n; ++ i) {
			if (chain[t[(st + n - i) % n]]) {
				len[t[(st + n -  i) % n]] = res;
				res = 0;
			}
			else ++ res;
		}
		len[t[st]] = res;
		for (int i : t) {
			if (!chain[i]) continue;
			if (chain[i] > len[i] + 1) ans = 0;
			if (chain[i] < len[i] + 1) (ans *= 2) %= MOD;
		}
	}
	printf("%d\n", ans);
}