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<queue>
#include<assert.h>
#include<tuple>
#include<string>
#include<algorithm>
#include<iostream>
#include<map>
#include<string.h>
#include<vector>
#include<math.h>
#include<stdlib.h>
#include<set>
#include<ctype.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
typedef tuple<int,int,int> t3;

const int MX = 1 << 20;
const int MM = 1000000007;

int D[MX], vst[MX], cnt[MX], cycle[MX];
	ll T[MX], U[MX], V[MX];
int N;

void dfs(int x, int c = 1){
	if( vst[x] ){
		if( vst[x] == -1 ) cnt[x] = c - 1;
		else{
			int t = x;
			do{
				cycle[D[t]] = t;
				t = D[t];
			}while(t != x);
			cnt[x] = vst[x] - 1;
		}
		return;
	}
	vst[x] = c;
	dfs(D[x], c+1);
	vst[x] = -1;
}

int indeg[MX];

int main()
{
	scanf("%d", &N);
	for(int i = 1; i <= N; i++) scanf("%d", D+i), indeg[D[i]]++;
	for(int i = 1; i <= N; i++){
		if( indeg[i] >= 3 ) return !printf("0\n");
	}
	for(int i = 1; i <= N; i++){
		if( vst[i] || indeg[i] ) continue;
		dfs(i);
	}
	for(int i = 1; i <= N; i++){
		if(vst[i]) continue;
		dfs(i);
	}
	for(int i = 1; i <= N; i++) if( !cycle[i] && cnt[i] ) return !printf("0\n");

	ll ans = 1;
	for(int i = 1; i <= N; i++){
		if( !cnt[i] ) continue;
		int x = i;
		for(int j = 1; j < cnt[i]; j++){
			x = cycle[x];
			if( cnt[x] ) return !printf("0\n");
		}
		if( !cnt[cycle[x]] ) ans = ans*2 % MM;
	}

	for(int i = 1; i <= N; i++) vst[i] = 0;
	map<int, int> L;
	int c1 = 0;
	for(int i = 1; i <= N; i++){
		if( vst[i] || !cycle[i] ) continue;
		int tt = 0, ch = 1;
		int x = i;
		do{
			x = D[x]; vst[x] = 1;
			if( cnt[x] ) ch = 0;
			tt++;
		}while(x != i);
		if( ch ) L[tt] += 1;
	}
	for(auto c : L){
		T[0] = 1; T[1] = c.first >= 2 && c.first%2 == 1 ? 2 : 1;
		for(int i = 2; i <= c.second; i++){
			T[i] = (T[i-1] * T[1] + T[i-2] * c.first % MM * (i-1)) % MM;
		}
		ans = ans * T[c.second] % MM;
	}
	printf("%lld\n", ans);
}