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 + 9, P = 1e9 + 7;

int a[N], n, Gr[N], s[N], t, la, h[N], sh, f[N], ans = 1;
bool v[N], inh[N], is[N];
vector<int>V[N];
unordered_map<int, int>T;

void Ext () { puts("0"); exit(0); }

void Dfs (int x, int fr) {
	is[x] = 1; s[++t] = x; v[x] = 1;
	for (auto v : V[x]) if (v != fr) {
		if (is[v]) {
			la = v;
			break ;
		} else {
			Dfs(v, x);
			if (la != -2) break ;
		}
	} else fr = -1;
	if (la > 0) {
		h[sh++] = x;
		inh[x] = sh;
		if (Gr[x] > 3) Ext();
		if (x == la) la = -1;
	}
	is[x] = 0; --t;
}

namespace T1 {
	void Dfs (int u, int fa) {
		if (!inh[u]) {
			v[u] = 1;
			if (Gr[u] > 2) Ext();
		}
		for (auto v : V[u]) if (!inh[v] && v != fa) {
			Dfs(v, u);
			f[u] = f[v] + 1;
		}
	}
	int main () {
		for (int i = 0; i < sh; ++i) Dfs(h[i], 0);
		int ans = 1, i = 0, j, k;
		while (i < sh && !f[h[i]]) ++i; if (i == sh) return ++T[sh], 1;
		do if (f[h[i]]) {
			for (j = (i + 1) % sh, k = 1; !f[h[j]]; j = (j + 1) % sh, ++k);
			int ret = 0;
			if (f[h[i]] < k) ++ret;
			if (f[h[i]] <= k) ++ret;
			ans = 1ll * ans * ret % P;
			if (j <= i) break ;
		} while (i = j, 1);
		return ans;
	}
}

int Sol (int m, int n) {
	f[0] = f[1] = 1; int b = 1 + (m > 1 && (m & 1));
	for (int i = 1; i <= n; ++i) f[i] = (1ll * f[i - 2] * m % P * (i - 1) + f[i - 1] * b) % P;
	return f[n];
}

int main () {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		V[i].emplace_back(a[i]), V[a[i]].emplace_back(i);
		++Gr[i]; ++Gr[a[i]];
	}
	for (int i = 1; i <= n; ++i) if (!v[i]) {
		la = -2, sh = 0, Dfs(i, 0);
		if (sh > 1 && a[h[0]] == h[1]) reverse(h, h + sh);
		ans = 1ll * ans * T1::main() % P;
	}
	for (auto v : T) ans = 1ll * ans * Sol(v.first, v.second) % P;
	printf("%d\n", ans);
	return 0;
}