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 <stdio.h>
#include <algorithm>
#include <queue>
using namespace std;

const long long mod = 1000000007;
long long inv[100100]={0,1},fact[100100]={1,1},ifact[100100]={1,1};
int N,P[100100],D[100100],L[100100],G[100100],X[100100],S[200200];
queue<int> Q;

int main()
{
	scanf ("%d",&N);
	for (int i=1;i<=N;i++) scanf ("%d",&P[i]), D[P[i]]++;
	for (int i=1;i<=N;i++){
		if (D[i] >= 3){
			puts("0");
			return 0;
		}
		if (D[i] == 0) Q.push(i);
	}

	while (!Q.empty()){
		int x = Q.front(); Q.pop();

		if (L[P[x]]){
			puts("0");
			return 0;
		}
		L[P[x]] = L[x] + 1;
		if (--D[P[x]] == 0) Q.push(P[x]);
	}
	
	long long ans = 1;
	for (int i=1;i<=N;i++) if (D[i] == 1){
		int x = i, c = 0;
		while (D[x] == 1){
			X[c] = x;
			S[c] = (L[x] > 0);
			c++;

			D[x] = 0;
			x = P[x];
		}
		reverse(X,X+c);
		reverse(S,S+c);
		for (int i=0;i<c;i++) S[i+c] = S[i];
		for (int i=1;i<c*2;i++) S[i] += S[i-1];

		if (S[c-1] == 0) G[c]++;
		else{
			for (int i=0;i<c;i++){
				int x = X[i], v = 0;
				if (L[x]){
					if (L[x] <= c && S[i+L[x]-1] - S[i] == 0) v++;
					if (L[x] <= c-1 && S[i+L[x]] - S[i] == 0) v++;
					ans = ans * v % mod;
				}
			}
		}
	}

	for (int i=2;i<=N;i++){
		inv[i] = (mod - mod / i) * inv[mod % i] % mod;
		fact[i] = fact[i-1] * i % mod;
		ifact[i] = ifact[i-1] * inv[i] % mod;
	}

	for (int i=1;i<=N;i++) if (G[i]){
		long long coeff = (i % 2 == 1 && i > 1 ? 2 : 1);
		long long sum = 0, now = 1;
		for (int j=0;j<G[i];j++) now = now * coeff % mod;
		for (int j=0;j<=G[i]/2;j++){
			sum = (sum + now * fact[G[i]] % mod * ifact[j*2] % mod * ifact[G[i]-j*2]) % mod;
			now = now * (j * 2 + 1) % mod;
			now = now * i % mod;
			now = now * inv[coeff] % mod;
			now = now * inv[coeff] % mod;
		}
		ans = ans * sum % mod;
	}

	printf ("%lld\n",ans);

	return 0;
}