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 <cstdio>

typedef long long LL;
const int Mod = 1000000007;
const int MN = 100005;

int N, p[MN], c[MN], d[MN], k[MN], g[MN], Ans;
int q[MN], l, r;

int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; ++i) scanf("%d", &p[i]), ++d[p[i]];
	for (int i = 1; i <= N; ++i) if (d[i] > 2) return puts("0"), 0;
	for (int i = 1; i <= N; ++i) if (!d[i]) q[++r] = i;
	while (l < r) {
		int u = q[++l], x = p[u];
		k[x] = k[u] + 1;
		if (++c[x] == d[x]) q[++r] = x;
	}
	for (int i = 1; i <= N; ++i) if (c[i] > 1) return puts("0"), 0;
	Ans = 1;
	for (int i = 1; i <= N; ++i) if (c[i] < d[i]) {
		q[r = 1] = i;
		for (int x = p[i]; x != i; x = p[x]) q[++r] = x;
		int lst = 0;
		for (int j = 1; j <= r; ++j) if (c[q[j]]) lst = j;
		for (int j = 1; j <= r; ++j) c[q[j]] = d[q[j]];
		if (!lst) { ++g[r]; continue; }
		lst -= r;
		for (int j = 1; j <= r; ++j) if (k[q[j]]) {
			if (k[q[j]] > j - lst) return puts("0"), 0;
			if (k[q[j]] < j - lst) Ans = 2 * Ans % Mod;
			lst = j;
		}
	}
	for (int i = 1; i <= N; ++i) if (g[i]) {
		int x = 1, y = 1 + (i >= 3 && i & 1), z;
		for (int j = 2; j <= g[i]; ++j)
			z = ((1 + (i >= 3 && i & 1)) * y + (LL)x * (j - 1) * i) % Mod, x = y, y = z;
		Ans = (LL)Ans * y % Mod;
	}
	printf("%d\n", Ans);
	return 0;
}