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>
#define xx first
#define yy second
#define mp make_pair
#define pb push_back
#define mset(x, y) memset(x, y, sizeof x)
#define mcpy(x, y) memcpy(x, y, sizeof x)
using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

inline int Read()
{
	int x = 0, f = 1, c = getchar();
	for (; !isdigit(c); c = getchar())
		if (c == '-')
			f = -1;
	for (;  isdigit(c); c = getchar())
		x = x * 10 + c - '0';
	return x * f;
}

const int MAXN = 100005;
const int mod = 1e9 + 7;

int n, ans = 1, a[MAXN], c[MAXN], d[MAXN], f[MAXN], cnt[MAXN];
bool v[MAXN];

inline int Dp(int l, int c)
{
	int t = ((l & 1) && (l ^ 1)) + 1;
	f[0] = 1, f[1] = t;
	for (int i = 2; i <= c; i ++)
		f[i] = (1LL * f[i - 1] * t + 1LL * f[i - 2] * (i - 1) % mod * l) % mod;
	return f[c];
}

int main()
{
#ifdef wxh010910
	freopen("data.in", "r", stdin);
#endif
	n = Read();
	for (int i = 1; i <= n; i ++)
		a[i] = Read(), d[a[i]] ++;
	for (int i = 1; i <= n; i ++)
		if (d[a[i]] > 2)
			return puts("0"), 0;
	for (int i = 1; i <= n; i ++)
		if (!d[i])
		{
			int x = i, len = 0;
			while (d[x] < 2)
				v[x] = 1, len ++, x = a[x];
			f[x] = len;
		}
	for (int i = 1; i <= n; i ++)
		if (!v[i])
		{
			int x = i, len = 0;
			bool flg = false;
			while (!v[x])
				v[x] = 1, c[len ++] = x, flg |= f[x], x = a[x];
			if (i ^ x)
				return puts("0"), 0;
			if (!flg)
				cnt[len] ++;
			else
			{
				int sta = 0, lst;
				while (!f[c[sta]])
					sta ++;
				lst = sta;
				for (int j = (sta + 1) % len; j ^ sta; j = (j + 1) % len)
					if (f[c[j]])
					{
						int x = (j - lst + len) % len;
						if (x < f[c[j]])
							return puts("0"), 0;
						if (x > f[c[j]])
							ans = (ans << 1) % mod;
						lst = j;
					}
				int x = (sta - lst + len - 1) % len + 1;
				if (x < f[c[sta]])
					return puts("0"), 0;
				if (x > f[c[sta]])
					ans = (ans << 1) % mod;
			}
		}
	for (int i = 1; i <= n; i ++)
		if (cnt[i])
			ans = 1LL * ans * Dp(i, cnt[i]) % mod;
	return printf("%d\n", ans), 0;
}