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 + 100, MOD = 1000 * 1000 * 1000 + 7;

int sum(int a, int b) {
	a += b;
	if (a < 0)
		a += MOD;
	else if (a >= MOD)
		a -= MOD;
	return a;
}
int mul(int a, int b) {
	return 1LL * a * b % MOD;
}
void _sum(int &a, int b) {
	a = sum(a, b);
}
void _mul(int &a, int b) {
	a = mul(a, b);
}

int n, ans = 1, out[N], cnt[N], fac[N], inv[N], val[N], have[N], power[3][N];
bool mark[N];
vector<int> in[N];

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

void pre_pro() {
	fac[0] = 1;
	for (int i = 1; i < N; i++)
		fac[i] = mul(fac[i - 1], i);
	inv[0] = inv[1] = 1;
	for (int i = 2; i < N; i++)
		inv[i] = mul(MOD - MOD / i, inv[MOD % i]);
	for (int i = 2; i < N; i++)
		_mul(inv[i], inv[i - 1]);
	val[0] = 1;
	for (int i = 1; i < N; i++)
		val[i] = mul(2 * i - 1, val[i - 1]);
	for (int i = 1; i <= 2; i++) {
		power[i][0] = 1;
		for (int j = 1; j < N; j++)
			power[i][j] = mul(power[i][j - 1], i);
	}
}

int c(int m, int n) {
	return (m > n? 0: mul(fac[n], mul(inv[m], inv[n - m])));
}

void input() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> out[i];
		in[--out[i]].push_back(i);
	}
}

void check() {
	for (int i = 0; i < n; i++)
		if (in[i].size() > 2)
			ZERO();
}

void go(int v, int now = 0) {
	if (cnt[v])
		ZERO();
	cnt[v] = now;
	if (in[v].size() > 1)
		return;
	mark[v] = true;
	go(out[v], now + 1);
}

void set_len() {
	for (int i = 0; i < n; i++)
		if (in[i].empty())
			go(i);
}

void dfs(int v, vector<int> *vec) {
	mark[v] = true;
	vec->push_back(v);
	if (mark[out[v]] == false)
		dfs(out[v], vec);
}

bool cycle(vector<int> vec) {
	for (int v: vec)
		if (cnt[v])
			return false;
	return true;
}

void f(vector<int> vec) {
	vector<int> X;
	for (int i = 0; i < vec.size(); i++)
		if (cnt[vec[i]])
			X.push_back(i);
	X.push_back(X[0]);
	for (int i = 1; i < X.size(); i++) {
		int a = (X[i] - X[i - 1] + vec.size()), b = cnt[vec[X[i]]];
		if (a > vec.size())
			a -= vec.size();
		if (b > a)
			ZERO();
		else if (b < a)
			_mul(ans, 2);
	}
}

void find_cycles() {
	for (int v = 0; v < n; v++)
		if (mark[v] == false) {
			vector<int> vec;
			dfs(v, &vec);
			if (cycle(vec))
				have[vec.size()]++;
			else
				f(vec);
		}
}

int handle(int l) {
	int res = 0;
	int p = 1 + ((l & 1) && (l > 1));
	int now = 1;
	for (int i = 0; 2 * i <= have[l]; i++) {
		_sum(res, mul(mul(c(2 * i, have[l]), val[i]), mul(power[p][have[l] - 2 * i], now)));
		_mul(now, l);
	}
	return res;
}

void check_cycles() {
	for (int i = 1; i < N; i++)
		_mul(ans, handle(i));
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	pre_pro();
	input();
	check();
	set_len();
	find_cycles();
	check_cycles();
	cout << ans;
}