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 <cstdio>
#include <algorithm>
using namespace std;

#define ILLEGAL puts("0"), exit(0)

const int MAXN = 100000;
const int MOD = int(1E9) + 7;
const int INV2 = (MOD + 1) / 2;

int pow_mod(int b, int p) {
	int ret = 1;
	for(int i=p;i;i>>=1,b=1LL*b*b%MOD)
		if( i & 1 ) ret = 1LL*ret*b%MOD;
	return ret;
}

int fct[MAXN + 5], ifct[MAXN + 5], f[MAXN + 5];
int comb(int n, int m) {
	return 1LL*fct[n]*ifct[m]%MOD*ifct[n-m]%MOD;
}
void init() {
	fct[0] = 1;
	for(int i=1;i<=MAXN;i++)
		fct[i] = 1LL*fct[i-1]*i%MOD;
	ifct[MAXN] = pow_mod(fct[MAXN], MOD - 2);
	for(int i=MAXN-1;i>=0;i--)
		ifct[i] = 1LL*ifct[i+1]*(i+1)%MOD;
	f[0] = 1;
	for(int i=2;i<=MAXN;i+=2)
		f[i] = 1LL*comb(i, 2)*f[i-2]%MOD*pow_mod(i/2, MOD-2)%MOD;
}

int a[MAXN + 5], N;
bool tag[MAXN + 5], vis[MAXN + 5];
int cnt[MAXN + 5], b[MAXN + 5], ind[MAXN + 5];

int main() {
	init(), scanf("%d", &N);
	for(int i=1;i<=N;i++)
		scanf("%d", &a[i]), ind[a[i]]++;
	for(int i=1;i<=N;i++)
		if( ind[i] >= 3 ) ILLEGAL;
	for(int i=1;i<=N;i++) {
		if( ind[i] == 2 ) {
			if( tag[i] ) continue;
			int p = i;
			while( !vis[p] )
				vis[p] = true, p = a[p];
			if( p != i ) ILLEGAL;
			p = i;
			do {
				tag[p] = true, p = a[p];
			}while( p != i );
		}
	}
	for(int i=1;i<=N;i++) {
		if( ind[i] == 0 ) {
			int t = 0, p = i;
			while( !tag[p] )
				vis[p] = true, t++, p = a[p];
			b[p] = t;
		}
	}
	int ans = 1;
	for(int i=1;i<=N;i++) {
		if( b[i] ) {
			int t = 0, p = i;
			do {
				t++, p = a[p];
			}while( !b[p] );
			if( t < b[p] ) ILLEGAL;
			else if( t > b[p] ) ans = 2LL*ans%MOD;
		}
	}
	for(int i=1;i<=N;i++) {
		if( !vis[i] ) {
			int t = 0, p = i;
			do {
				vis[p] = true, t++, p = a[p];
			}while( !vis[p] );
			cnt[t]++;
		}
	}
	for(int i=1;i<=N;i++) {
		int del = 0;
		for(int j=0;j<=cnt[i];j+=2) {
			int tmp = 1;
			tmp = 1LL*tmp*comb(cnt[i], j)%MOD*f[j]%MOD*pow_mod(i, j/2)%MOD;
			if( (i & 1) && i != 1 ) {
				tmp = 1LL*tmp*pow_mod(2, cnt[i] - j)%MOD;
			}
			del = (del + tmp) % MOD;
		}
		ans = 1LL*ans*del%MOD;
	}
	printf("%d\n", ans);
}