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 mod = 1e9+7;

int n;

const int maxn = 100010;
int p[maxn];
int ind[maxn];
bool vis[maxn];
int pos[maxn];
int feet[maxn];

map<int, int> cir;

int dp[maxn];
int DP(int m,int n) {
	long long s = 1 + ((m > 1) & (m & 1));
	long long p = m;
	dp[0] = 1;
	dp[1] = s;
	for(int i = 2; i <= n; ++i) {
		dp[i] = (s * dp[i-1] + p * (i-1) % mod * dp[i-2]) % mod;
	}
	return dp[n];
}

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) { scanf("%d", &p[i]); ind[p[i]] += 1; }
	for(int i = 1; i <= n; ++i) if(ind[i] > 2) { puts("0"); return 0; }
	for(int i = 1; i <= n; ++i) if(ind[i] == 0) {
		int j, l = 0;
		for(j = i; ind[j] < 2; j = p[j]) vis[j] = true, l += 1;
		feet[j] = l;
	}
	int ans = 1;
	for(int i = 1; i <= n; ++i) if(!vis[i]) {
		int l = 0, j;
		for(j = i; !vis[j]; j = p[j]) vis[j] = true, pos[l++] = j;
		if(i!=j) ans = 0;
		int last = 0;
		for(int j = 0; j < l; ++j) if(feet[pos[j]] > 0) last = j - l;
		if(last == 0) { cir[l]++; continue; }
		for(int j = 0; j < l; ++j) if(feet[pos[j]] > 0) {
			if(j - last > feet[pos[j]]) ans = (ans << 1) % mod;
			else if(j - last < feet[pos[j]]) ans = 0;
			last = j;
		}
	}
	for(auto e: cir) ans = 1ll * ans * DP(e.first, e.second) % mod;
	cout << ans << endl;
	return 0;
}