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<vector>
using namespace std;
const int MAXN = 100000;
const int MOD = int(1E9) + 7;
vector<int>rev[MAXN + 5];
int a[MAXN + 5], f[MAXN + 5], dis[MAXN + 5], dep[MAXN + 5];
bool vis[MAXN + 5], vis2[MAXN + 5], tag[MAXN + 5];
int siz, del, ans = 1, tmp;
void dfs1(int x) {
	siz++;
	if( rev[x].size() >= 2 ) tmp = x;
	vis[x] = true;
	for(int i=0;i<rev[x].size();i++)
		if( !vis[rev[x][i]] ) dfs1(rev[x][i]);
	if( !vis[a[x]] ) dfs1(a[x]);
}
int dfs2(int x) {
	if( rev[x].size() == 0 ) return 1;
	else if( rev[x].size() == 1 ) {
		int d = dfs2(rev[x][0]);
		if( d == -1 ) return -1;
		else return d + 1;
	}
	else return -1;
}
int fact[MAXN + 5], inv[MAXN + 5], fun[MAXN + 5];
int pow_mod(int b, int p) {
	int ret = 1;
	while( p ) {
		if( p & 1 ) ret = 1LL*ret*b%MOD;
		b = 1LL*b*b%MOD;
		p >>= 1;
	}
	return ret;
}
void init() {
	fact[0] = 1;
	for(int i=1;i<=MAXN;i++)
		fact[i] = 1LL*fact[i-1]*i%MOD;
	inv[MAXN] = pow_mod(fact[MAXN], MOD-2);
	for(int i=MAXN-1;i>=0;i--)
		inv[i] = 1LL*inv[i+1]*(i+1)%MOD;
	fun[0] = 1;
	for(int i=1;i<=MAXN;i++)
		fun[i] = 1LL*fun[i-1]*(2*i-1)%MOD;
}
int comb(int n, int m) {
	return 1LL*fact[n]*inv[m]%MOD*inv[n-m]%MOD;
}
int main() {
	init(); int N;
	scanf("%d", &N);
	for(int i=1;i<=N;i++) {
		scanf("%d", &a[i]);
		rev[a[i]].push_back(i);
	}
	for(int i=1;i<=N;i++)
		if( !vis[i] ) {
			tmp = -1; siz = 0; dfs1(i);
 			if( tmp != -1 ) {
 				int nw = tmp;
 				do {
 					vis2[nw] = true;
 					nw = a[nw];
				}while( !vis2[nw] );
				if( nw != tmp ) {
					ans = 0;
					continue;
				}
				int p = nw; del = 1;
				do {
					tag[p] = true;
					if( rev[p].size() > 2 ) 
						del = 0;
					p = a[p];
				}while( p != nw );
				if( del == 0 ) {
					ans = 0;
					continue;
				}
				int tmp;
				do {
					if( rev[p].size() == 2 )  {
						dep[p] = tag[rev[p][0]] ? dfs2(rev[p][1]) : dfs2(rev[p][0]);
						if( dep[p] == -1 ) del = 0;
						tmp = p;
					}
					p = a[p];
				}while( p != nw );
				p = nw = tmp;
				int lst = 0;
				do {
					p = a[p]; lst++;
					dis[p] = lst;
					if( rev[p].size() == 2 ) {
						lst = 0;
						if( dis[p] > dep[p] ) del = 2LL*del%MOD;
						else if( dis[p] < dep[p] ) del = 0;
					}
				}while( p != nw );
				ans = 1LL*ans*del%MOD;
			}
			else f[siz]++;
		}
	for(int i=1;i<=N;i++) {
		if( (i & 1) && i != 1 ) {
			del = 0;
			for(int j=0;j<=f[i];j+=2)
				del = (del + 1LL*comb(f[i], j)*fun[j/2]%MOD*pow_mod(i, j/2)%MOD*pow_mod(2, f[i]-j)%MOD)%MOD;
			ans = 1LL*del*ans%MOD;
		}
		else {
			del = 0;
			for(int j=0;j<=f[i];j+=2)
				del = (del + 1LL*comb(f[i], j)*fun[j/2]%MOD*pow_mod(i, j/2)%MOD)%MOD;
			ans = 1LL*del*ans%MOD;
		}
	}
	printf("%d\n", ans);
}