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;
typedef pair<int, int> P;
template<typename T> inline void chkmin(T &a, const T &b) { a = a < b ? a : b; }
template<typename T> inline void chkmax(T &a, const T &b) { a = a > b ? a : b; }

const int MAXN = 100005, MOD = 1e9 + 7;
int n, arr[MAXN], vis[MAXN], cir[MAXN], inc[MAXN];
int dep[MAXN], cnt[MAXN];
LL fac[MAXN], inv[MAXN];
vector<int> gra[MAXN];

LL modpow(LL a, int b) {
	LL res = 1;
	for (; b; b >>= 1) {
		if (b & 1) res = res * a % MOD;
		a = a * a % MOD;
	}
	return res;
}

int dfs(int u) {
	int cnt = 0, d = 0;
	for (int v : gra[u]) {
		if (inc[v]) continue;
		if (cnt++) {
			puts("0");
			exit(0);
		}
		d = dfs(v) + 1;
	}
	return d;
}

int main() {
	scanf("%d", &n);
	fac[0] = 1;
	for (int i = 1; i <= n; i++) {
		scanf("%d", arr + i);
		gra[arr[i]].push_back(i);
		fac[i] = fac[i - 1] * i % MOD;
	}
	inv[n] = modpow(fac[n], MOD - 2);
	for (int i = n; i > 0; i--) inv[i - 1] = inv[i] * i % MOD;
	
	LL ans = 1;
	for (int i = 1; i <= n; i++) if (!vis[i]) {
		int j = i, tot = 0;
		for (; !vis[j]; j = arr[j]) vis[j] = i;
		if (vis[j] != i) continue;
		for (int k = arr[j]; k != j; k = arr[k])
			cir[tot++] = k, inc[k] = 1;
		cir[tot++] = j, inc[j] = 1;
		memset(dep, 0, sizeof(int) * tot);
		bool flag = false;
		for (int k = 0; k < tot; k++) {
			int t = cir[k];
			if (gra[t].size() == 1) continue;
			dep[k] = dfs(t);
			flag = true;
		}
		if (flag) {
			for (int k = 0; k < tot; k++) if (dep[k]) {
				int nxt = 0;
				for (int j = (k - 1 + tot) % tot;; j = (j - 1 + tot) % tot) {
					if (dep[j]) break;
					++nxt;
				}
				if (nxt < dep[k] - 1) {
					puts("0");
					return 0;
				}
				if (nxt >= dep[k]) ans = ans * 2 % MOD;
			}
		} else ++cnt[tot];
	}
	for (int i = 1; i <= n; i++) if (cnt[i]) {
		LL pw = 1, t = (LL)i * (MOD + 1) / 2 % MOD, sum = 0;
		if (i & 1 && i > 1) pw = modpow(2, cnt[i]), t = (LL)i * (MOD + 1) / 8 % MOD;
		for (int j = 0; 2 * j <= cnt[i]; j++) {
			sum = (sum + pw * inv[cnt[i] - 2 * j] % MOD * inv[j]) % MOD;
			pw = pw * t % MOD;
		}
		ans = ans * sum % MOD * fac[cnt[i]] % MOD;
	}
	printf("%lld\n", ans);
	return 0;
}