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 LL long long
#define INF 0x7FFFFFFF//or 0x3f3f3f3f ? -Wall
using namespace std;

template<class T> inline
void read(T& x) {
	int f = 1; x = 0;
	char ch = getchar();

	while (ch < '0' || ch > '9')   {if (ch == '-') f = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
	x *= f;
}

/*============ Header Template ============*/

const int N = 100000 + 5;
const int mo = 1000000007;

int n;
int a[N], in[N], c[N], l[N], deg[N], vis[N], ch[N], pos[N];
LL f[N];
queue<int> Q;
std::vector<int> zkx;

void Topo() {
	for (int i = 1; i <= n; i++) if (!in[i]) Q.push(i);
	while (!Q.empty()) {
		int x = Q.front(); Q.pop();
		ch[x] = 1;
		if (--in[a[x]] == 0) Q.push(a[x]);
	}
}

int main() {
	read(n);
	for (int i = 1; i <= n; i++) read(a[i]), in[a[i]]++, deg[a[i]]++;
	for (int i = 1; i <= n; i++) if (in[a[i]] > 2) {printf("0\n"); return 0;}
	Topo();
	for (int i = 1; i <= n; i++) if (ch[i] && deg[i] > 1) {printf("0\n"); return 0;}
	for (int i = 1; i <= n; i++)
		if (ch[i] && !deg[i]) {
			int x = i, cnt = 0;
			while (ch[x]) {cnt++; x = a[x];}
			l[x] = cnt;
		}
	//for (int i = 1; i <= n; i++) printf("%d ", l[i]); printf("\n");
	LL ans = 1;
	for (int i = 1; i <= n; i++) if (!ch[i] && !vis[i]) {
			int x = i, cnt = 0; LL tmp = 1;
			zkx.clear();
			while (!vis[x]) {
				vis[x] = 1; cnt++;
				if (l[x]) zkx.push_back(x);
				pos[x] = cnt; x = a[x];
			}
			if (!zkx.size()) {c[cnt]++; continue;}
			//printf("%d\n", cnt);
			zkx.push_back(0); pos[0] = pos[zkx[0]] + cnt; l[0] = l[zkx[0]];
			for (int i = 1; i < zkx.size(); i++) {
				int l1 = l[zkx[i]];
				int l2 = pos[zkx[i]] - pos[zkx[i - 1]];
				if (l1 == l2) continue;
				(tmp *= (l1 < l2 ? 2LL : 0)) %= mo;
			}
			(ans *= tmp) %= mo;
		}
	//printf("%lld\n", ans);
	//for (int i = 1; i <= n; i++) printf("%d ", c[i]); printf("\n");
	for (int k = 1; k <= n; k++) {
		if (!c[k]) continue;
		LL w = (k > 1 && (k & 1) ? 2 : 1);
		f[0] = 1; f[1] = w;
		for (int i = 2; i <= c[k]; i++)
			f[i] = (f[i - 1] * w % mo + f[i - 2] * (i - 1) % mo * k % mo) % mo;
		(ans *= f[c[k]]) %= mo;
	}
	printf("%lld\n", (ans + mo) % mo);
	return 0;
}