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>

typedef long long ll;
typedef long long llong;
typedef long double ld;
typedef unsigned long long ull;

using namespace std;

void ex() {
	cout << 0 << "\n";
	exit(0);
}

const ll MOD = 1e9 + 7;
ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}
const int MAXN = 120000;

int was[MAXN];
int fl[MAXN];
vector<int> vv;
int go[MAXN * 2];
vector<int> beds[MAXN];
int a[MAXN];
int cc[MAXN];
ll fc[MAXN];
ll bfc[MAXN];
int n;
int tm1;
int lst[MAXN];

void dfs1(int v) {
	if (was[v]) {
		if (lst[v] == tm1)
			fl[v] = 1;
		return;
	}
	was[v] = 1;
	lst[v] = tm1;
	dfs1(a[v]);
}

void dfs2(int v) {
	vv.push_back(v);
	was[v] = 1;
	if (!was[a[v]])
		dfs2(a[v]);
}

int dfs3(int v) {
	if (beds[v].size() >= 2)
		ex();
	int a = 1;
	for (int u: beds[v])
		a += dfs3(u);
	return a;
}

int main() {
	scanf("%d", &n);
	fc[0] = bfc[0] = 1;
	for (int i = 1; i <= n; ++i)
		fc[i] = (fc[i - 1] * i) % MOD, bfc[i] = pw(fc[i], MOD - 2);
	for (int i = 0; i < n; ++i) {
		scanf("%d", a + i), --a[i];
		beds[a[i]].push_back(i);
	}
	for (int i = 0; i < n; ++i) {
		if (was[i])
			continue;
		++tm1;
		dfs1(i);
	}
	memset(was, 0, sizeof(was));
	ll ans = 1;
	for (int i = 0; i < n; ++i) {
		if (was[i] || !fl[i])
			continue;
		vv.clear();
		dfs2(i);
		int f = 0;
		for (int i = 0; i < vv.size(); ++i) {
			if (beds[vv[i]].size() > 2)
				ex();
			go[i] = 0;
			for (int j: beds[vv[i]])
				if (!was[j])
					f = 1, go[i] = dfs3(j);
		}
		if (!f) {
			++cc[vv.size()];
		}
		else {
			for (int i = 0; i < vv.size(); ++i)
				go[i + vv.size()] = go[i];
			int lst = 0;
			for (int i = 0; i < vv.size(); ++i)
				if (go[i])
					lst = i;
			for (int i = vv.size(); i < 2 * vv.size(); ++i) {
				if (!go[i])
					continue;
				if (i - lst < go[i])
					ex();
				if (i - lst > go[i])
					ans = (ans * 2) % MOD;
				lst = i;
			}
		}
	}
	ll B2 = pw(2, MOD - 2);
	for (int i = 1; i <= n; ++i) {
		if (!cc[i])
			continue;
		ll go = 0;
		if (i != 1 && i % 2 == 1) {
			for (int j = 0; j * 2 <= cc[i]; ++j) {
				go = (go + pw(2, cc[i] - j * 2) * pw(i, j) % MOD * fc[cc[i]] % MOD * bfc[cc[i] - j * 2] % MOD * pw(B2, j) % MOD * bfc[j] % MOD) % MOD;
			}
		}
		else {
			for (int j = 0; j * 2 <= cc[i]; ++j) {
				go = (go + pw(i, j) % MOD * fc[cc[i]] % MOD * bfc[cc[i] - j * 2] % MOD * pw(B2, j) % MOD * bfc[j] % MOD) % MOD;
			}
		}
		ans = (ans * go) % MOD;
	}
	cout << ans << "\n";
	return 0;
}