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(111111);
int modulo(1e9 + 7);
int a[N], stmp[N], zc[N], cnt[N], deg[N], rela[N], f[N];
bool vst[N], incyc[N];
int getr(int x) {
	int p(x);
	while(p != rela[p]) 
		p = rela[p];
	int p1(p); p = x;
	while(p != rela[p]) {
		int p2(rela[p]);
		rela[p] = p1;
		p = p2;	
	}
	return p1;
}
int main() {
	int n;
	scanf("%d", &n);
	for(int i(1); i <= n; i++) {
		scanf("%d", &a[i]);
		deg[a[i]]++;
		if(deg[a[i]] >= 3) {
			printf("0\n");
			return 0;
		}
	}
	int t(0);
	vector<vector<int> > cyc;
	fill(vst + 1, vst + 1 + n, false);
	for(int i(1); i <= n; i++) {
		if(!vst[i]) {
			int x(i);
			++t;
			while(!vst[x]) {
				stmp[x] = t;
				vst[x] = true;
				x = a[x];
			}
			if(stmp[x] == t) {
				int y(x);
				vector<int> vec;
				do {
					vec.push_back(y);
					incyc[y] = true;
					y = a[y];
				} while(y != x);
				cyc.push_back(vec);
			}
		}
	}
	for(int i(1); i <= n; i++) 
		if(!incyc[i] && deg[i] >= 2) {
			printf("0\n");
			return 0;
		}
	for(int i(1); i <= n; i++) 
		rela[i] = i;
	for(int i(1); i <= n; i++) {
		if(!incyc[i]) {
			rela[getr(i)] = getr(a[i]);
		}
	}
	for(int i(1); i <= n; i++)
		if(!incyc[i])
			cnt[getr(i)]++;
	int ans(1);
	for(int i(0); i < (int)cyc.size(); i++) {
		int len(cyc[i].size());
		int cz(0);
		for(int j(0); j < len; j++) {
			if(cnt[getr(cyc[i][j])]) {
				int c(0);
				for(int k((j - 1 + len) % len); k != j && cnt[getr(cyc[i][k])] == 0; k = (k - 1 + len) % len) {
					c++;
				}
				if(c + 1 == cnt[getr(cyc[i][j])]) {
				}else if(c + 1 > cnt[getr(cyc[i][j])]) {
					ans = (ans * 2 % modulo);
				}else {
					ans = 0;
				}
			}else {
				cz++;
			}
		}
		if(cz == len) {
			zc[len]++;
		}
	}
	for(int i(1); i <= n; i++) {
		if(zc[i]) {
			//cout << i << '!' << zc[i] << endl;
			f[1] = 1 + (i % 2 == 1 && i > 1);
			f[0] = 1;
			for(int j(2); j <= zc[i]; j++) {
				f[j] = ((1 + (i % 2 == 1 && i > 1)) * f[j - 1] + (j - 1ll) * i * f[j - 2]) % modulo;
			}
			ans = (long long)ans * f[zc[i]] % modulo;
		}
	}
	cout << ans << endl;
}