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;
#define MAXN	100005
#define P	1000000007
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
int n, a[MAXN], d[MAXN], cnt[MAXN], p[MAXN], len[MAXN];
bool visited[MAXN], used[MAXN], special[MAXN];
deque <int> Q;
long long dp[MAXN];
void add(long long &x, long long y) {
	x = (x + y) % P;
}
void times(long long &x, long long y) {
	x = x * y % P;
}
int main() {
	read(n);
	for (int i = 1; i <= n; i++)
		read(a[i]), d[a[i]]++;
	for (int i = 1; i <= n; i++)
		if (d[i] == 0) {
			visited[i] = true;
			Q.push_back(i);
		}
	while (!Q.empty()) {
		int tmp = Q.front();
		Q.pop_front();
		d[a[tmp]]--;
		if (d[a[tmp]] == 0) {
			visited[a[tmp]] = true;
			Q.push_back(a[tmp]);
		}
	}
	memset(d, 0, sizeof(d));
	for (int i = 1; i <= n; i++)
		d[a[i]]++;
	for (int i = 1; i <= n; i++)
		if (visited[i] && d[i] >= 2 || !visited[i] && d[i] >= 3) {
			printf("0\n");
			return 0;
		}
	for (int i = 1; i <= n; i++)
		if (!visited[i]) {
			p[a[i]] = i;
			if (!used[i]) {
				int pos = a[i], mx = d[i], len = 1;
				used[i] = true;
				while (pos != i) {
					mx = max(mx, d[pos]);
					len++; used[pos] = true;
					pos = a[pos];
				}
				if (mx <= 1) cnt[len]++;
				else {
					pos = a[i]; special[i] = true;
					while (pos != i) {
						special[pos] = true;
						pos = a[pos];
					}
				}
			}
		}
	long long ans = 1;
	for (int i = 1; i <= n; i++) {
		if (cnt[i] == 0) continue;
		dp[0] = 1;
		for (int j = 1; j <= cnt[i]; j++) {
			dp[j] = dp[j - 1];
			if (i & 1 && i > 1) add(dp[j], dp[j - 1]);
			if (j > 1) add(dp[j], dp[j - 2] * (j - 1) % P * i);
		}
		times(ans, dp[cnt[i]]);
	}
	for (int i = 1; i <= n; i++) {
		if (d[i]) continue;
		int pos = i, l = 0;
		while (!special[pos]) {
			l++, pos = a[pos];
		}
		len[pos] = l;
	}
	for (int i = 1; i <= n; i++) {
		if (len[i] == 0) continue;
		int pos = p[i], l = 1;
		while (!len[pos]) {
			l++, pos = p[pos];
		}
		if (l > len[i]) times(ans, 2);
		else if (l < len[i]) ans = 0;
	}
	cout << ans << endl;
	return 0;
}