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 <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

typedef long long s64;

inline int getint()
{
	static char c;
	while ((c = getchar()) < '0' || c > '9');

	int res = c - '0';
	while ((c = getchar()) >= '0' && c <= '9')
		res = res * 10 + c - '0';
	return res;
}

const int MaxN = 100000;
const int M = 1000000007;

inline int modpow(int a, const int &n)
{
	int res = 1;
	for (int i = n; i; i >>= 1)
	{
		if (i & 1)
			res = (s64)res * a % M;
		a = (s64)a * a % M;
	}
	return res;
}

int n;
int link[MaxN + 1];

int fact[MaxN + 1];
int rfact[MaxN + 1];

int prePow[MaxN + 1];

inline int binom(const int &n, const int &m)
{
	return (s64)fact[n] * rfact[m] % M * rfact[n - m] % M;
}

int dep[MaxN + 1];

int deg[MaxN + 1];
int ori[MaxN + 1];

int q_n, q[MaxN];

bool vis[MaxN + 1];

int cir_l, cir[MaxN + 1];

int sum[MaxN + 1];

int main()
{
	cin >> n;

	prePow[0] = 1;
	for (int i = 1; i <= n; ++i)
		prePow[i] = prePow[i - 1] * 2 % M;

	fact[0] = 1;
	for (int i = 1; i <= n; ++i)
		fact[i] = (s64)fact[i - 1] * i % M;
	rfact[n] = modpow(fact[n], M - 2);
	for (int i = n; i; --i)
		rfact[i - 1] = (s64)rfact[i] * i % M;

	for (int u = 1; u <= n; ++u)
	{
		int v = getint();
		++deg[link[u] = v];
		++ori[v];
	}

	q_n = 0;
	for (int u = 1; u <= n; ++u)
		if (!deg[u])
			q[q_n++] = u;
	for (int i = 0; i < q_n; ++i)
	{
		int u = q[i];
		dep[link[u]] = dep[u] + 1;

		if (!--deg[link[u]])
			q[q_n++] = link[u];
	}

	for (int u = 1; u <= n; ++u)
		if (ori[u] - deg[u] > 1)
		{
			cout << 0 << endl;
			return 0;
		}

	int res = 1;
	for (int u = 1; u <= n; ++u)
		if (!vis[u] && deg[u])
		{
			cir_l = 0;

			int sv = u;
			bool is_single = true;
			while (!vis[sv])
			{
				if (dep[sv] > 0)
					is_single = false;

				vis[sv] = true;
				cir[++cir_l] = sv;
				sv = link[sv];
			}

			if (is_single)
			{
				++sum[cir_l];
				continue;
			}

			for (int i = 1; i <= cir_l; ++i)
			{
				int sv = cir[i];
				if (dep[sv] > 0)
				{
					int pos = i, len = 0;
					for (int k = 1; ; ++k)
					{
						pos = pos == 1 ? cir_l : pos - 1;
						if (dep[cir[pos]] > 0)
						{
							len = k;
							break;
						}
					}

					if (len > dep[sv])
						res = res * 2 % M;
					else if (len < dep[sv])
					{
						cout << 0 << endl;
						return 0;
					}
				}
			}
		}

	for (int l = 1; l <= n; ++l)
		if (sum[l] > 0)
		{
			s64 p = 1, r = 0;
			for (int i = 0; i <= sum[l] / 2; ++i)
			{
				s64 ways = (s64)p * fact[i] % M;
				ways = (s64)ways * binom(sum[l], i * 2) % M;
				ways = (s64)ways * binom(i * 2, i) % M;
				ways = (s64)ways * modpow(prePow[i], M - 2) % M;
				if (l > 1 && (l & 1))
					ways = (s64)ways * prePow[sum[l] - i * 2] % M;

				r = (r + ways) % M;
				p = (s64)p * l % M;
			}

			res = (s64)res * r % M;
		}

	cout << res << endl;

	return 0;
}