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 <iostream>
#include <vector>

using namespace std;

const int MOD = 1000000007;

int solve(const vector<int>& A){
	int N = A.size();
	vector< vector<int> > back(N);
	for(int i=0;i<N;i++){
		back[A[i]].push_back(i);
		if(back[A[i]].size() >= 3) return 0;
	}
	vector<int> check(N, 0);
	long long mul = 1;
	for(int i=0;i<N;i++){
		if(check[i]) continue;
		if(back[i].size() < 2) continue;
		int cur = i;
		while(true){
			int p0 = back[cur][0];
			int p1 = back[cur][1];
			if(back[p0].size() > back[p1].size()) swap(p0, p1);
			int s0 = back[p0].size();
			int s1 = back[p1].size();
			if(s0 == 0 && s1 == 0) return 0;
			if(s0 + s1 >= 3) return 0;
			if(s0 == 0 && s1 == 1) mul = (2*mul)%MOD;
			int l0 = 0, l1 = 0;
			while(back[p0].size() == 1 && !check[p0]){ check[p0] = 1; p0 = back[p0][0]; ++l0; }
			while(back[p1].size() == 1 && !check[p1]){ check[p1] = 1; p1 = back[p1][0]; ++l1; }
			if(back[p0].size() != 2 && back[p1].size() != 2) return 0;
			if(back[p0].size() == 2 && back[p1].size() == 2) return 0;
			if(back[p0].size() == 2){ swap(p0, p1); swap(l0, l1); }
			if(s0 == 1 && s1 == 1){
				if(l1 > l0) mul = (2*mul)%MOD;
				else if(l1 < l0) return 0;
			}
			check[p0] = check[p1] = 1;
			cur = p1;
			if(cur == i) break;
		}
	}
	vector<int> cycleNum(N+1, 0);
	for(int i=0;i<N;i++){
		if(check[i]) continue;
		if(back[i].size() != 1) return 0;
		int l = 1, cur = back[i][0];
		while(cur != i){
			check[cur] = 1;
			if(back[cur].size() != 1) return 0;
			cur = back[cur][0];
			if(check[cur]) return 0;
			++l;
		}
		check[i] = 1;
		cycleNum[l]++;
	}
	vector<long long> inv(1000000);
	vector<long long> fact(1000000);
	vector<long long> factInv(1000000);
	vector<long long> pow2(1000000);
	inv[0] = inv[1] = 1;
	fact[0] = fact[1] = 1;
	pow2[0] = 1, pow2[1] = 2;
	factInv[0] = factInv[1] = 1;
	for(int i=2;i<inv.size();i++){
		inv[i] = inv[MOD%i] * (MOD - MOD/i) % MOD;
		fact[i] = fact[i-1] * i % MOD;
		factInv[i] = factInv[i-1] * inv[i] % MOD;
		pow2[i] = pow2[i-1] * 2 % MOD;
	}
	for(int i=1;i<=N;i++){
		if(!cycleNum[i]) continue;
		long long add = (i%2 == 1 && i >= 3 ? pow2[cycleNum[i]] : 1);
		long long cur = 1;
		for(int j=1;2*j<=cycleNum[i];j++){
			cur = (cur * (2*j-1)) % MOD;
			cur = (cur * (2*j)) % MOD;
			cur = (cur * i) % MOD;
			cur = (cur * inv[j]) % MOD;
			cur = (cur * inv[2]) % MOD;
			long long comb = fact[cycleNum[i]] * factInv[2*j] % MOD * factInv[cycleNum[i] - 2*j] % MOD;
			long long curAdd = comb * cur % MOD;
			if(i%2 == 1 && i >= 3){
				curAdd = curAdd * pow2[cycleNum[i] - 2*j] % MOD;
			}
			add = (add + curAdd) % MOD;
		}
		mul = (mul * add) % MOD;
	}
	return mul;
}

int main(){
	int N;
	while(cin >> N){
		vector<int> A(N);
		for(int i=0;i<N;i++){
			cin >> A[i];
			--A[i];
		}
		cout << solve(A) << endl;
	}
}