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 <cstdio>
#define MOD 1000000007
long long dp[100005], ans = 1;
int deg[100005], nxt[100005], app[100005], pre[100005];
bool vis[100005];
int main()
{
	// freopen("AGC008-E.in", "r", stdin);
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", nxt + i);
		deg[--nxt[i]]++;
	}
	for (int i = 0; i < n; i++)
	{
		if (deg[i] > 2)
		{
			puts("0");
			return 0;
		}
		if (deg[i] != 2 || vis[i])
			continue;
		int u = i;
		do
		{
			if (vis[u])
			{
				puts("0");
				return 0;
			}
			vis[u] = true;
			pre[nxt[u]] = u;
			u = nxt[u];
		}
		while (u != i);
	}
	for (int i = 0; i < n; i++)
	{
		if (deg[i])
			continue;
		int u = i, foot_len = 0, cyc_len = 0;
		while (!vis[u])
		{
			vis[u] = true;
			u = nxt[u];
			foot_len++;
		}
		do
		{
			u = pre[u];
			cyc_len++;
		}
		while (deg[u] == 1);
		if (foot_len < cyc_len)
			ans = ans * 2 % MOD;
		if (foot_len > cyc_len)
		{
			puts("0");
			return 0;
		}
	}
	for (int i = 0; i < n; i++)
	{
		if (vis[i])
			continue;
		int u = i, len = 0;
		do
		{
			vis[u] = true;
			u = nxt[u];
			len++;
		}
		while (u != i);
		app[len]++;
	}
	for (int i = 1; i <= n; i++)
	{
		dp[0] = 1;
		for (int j = 1; j <= app[i]; j++)
		{
			dp[j] = dp[j - 1] * ((i & 1 ^ 1) || i == 1 ? 1 : 2) % MOD;
			if (j >= 2)
				(dp[j] += dp[j - 2] * (j - 1) * i) %= MOD;
		}
		ans = ans * dp[app[i]] % MOD;
	}
	printf("%lld\n", ans);
	return 0;
}