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;

typedef long long ll;
const int maxn = 100005, mod = 1e9 + 7;

inline int gi()
{
	char c = getchar();
	while (c < '0' || c > '9') c = getchar();
	int sum = 0;
	while ('0' <= c && c <= '9') sum = sum * 10 + c - 48, c = getchar();
	return sum;
}

inline int add(int x, int y) {return x + y >= mod ? x + y - mod : x + y;}

int n, ans, a[maxn], cir[maxn], flen[maxn], sum[maxn], f[maxn], deg[maxn], vis[maxn];

void solvecir(int x)
{
	int len = 0, s = 0, lst = 0, slen = 0;
	while (cir[x]) {
		++len; cir[x] = 0;
		if (flen[x]) {
			if (!s) s = lst = len, slen = flen[x];
			else {
				ans = (ll)ans * ((flen[x] < len - lst) + (flen[x] <= len - lst)) % mod;
				lst = len;
			}
		}
		x = a[x];
	}
	if (!s) ++sum[len];
	else ans = (ll)ans * ((slen < len - lst + s) + (slen <= len - lst + s)) % mod;
}

void solve()
{
	for (int i = 1; i <= n; ++i) {
		if (deg[i]) continue;
		int x = i, len = 0;
		while (!cir[x]) x = a[x], ++len;
		flen[x] = len;
	}
	ans = 1;
	for (int i = 1; i <= n; ++i) if (cir[i]) solvecir(i);
	for (int i = 1; i <= n; ++i) {
		if (!sum[i]) continue;
		f[0] = 1;
		for (int j = 1; j <= sum[i]; ++j) {
			if (i > 1 && (i & 1)) f[j] = add(f[j - 1], f[j - 1]);
			else f[j] = f[j - 1];
			if (j > 1) f[j] = (f[j] + (ll)f[j - 2] * (j - 1) % mod * i) % mod;
		}
		ans = (ll)ans * f[sum[i]] % mod;
	}
}

int main()
{
	n = gi();
	for (int i = 1; i <= n; ++i) a[i] = gi(), ++deg[a[i]];
	for (int i = 1; i <= n; ++i) {
		if (vis[i]) continue;
		int x = i; while (!vis[x]) vis[x] = i, x = a[x];
		if (vis[x] != i) continue;
		while (!cir[x]) cir[x] = 1, x = a[x];
	}

	for (int i = 1; i <= n; ++i)
		if ((cir[i] && deg[i] > 2) || (!cir[i] && deg[i] > 1)) return puts("0"), 0;

	solve();
	printf("%d\n", ans);

	return 0;
}