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 <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <list>

using namespace std;
typedef pair<int, int> Pi;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) x.begin(), x.end()

int N, A[100010];
int deg[100010];
int cyc[100010];

map <int, int> OC;

int p[100010], z[100010];
int Find(int x){return p[x] == x ? x : p[x] = Find(p[x]); }
int chk[100010];

const int MOD = 1e9 + 7;
ll D[100010];
int d[100010];

int get(int X){
	int res = 1;
	vector <int> v; v.pb(d[X]);
	int t = A[X];
	while(t != X){
		v.pb(d[t]);
		t = A[t];
	}
	int L = sz(v);
	for(int S=0;S<L;S++)if(v[S] != 1){
		for(int j=0;j<L;){
			int t = v[(S-j+L)%L];
			if(t == 0){j++; continue; }
			for(int k=1;k<t;k++){
				if(v[(S-j-k+L+L)%L] > 0)return 0;
			}
			if(v[(S-j-t+L+L)%L] > 0){
				j += t;
			}
			else{
				j += t + 1;
				res = res * 2 % MOD;
			}
		}
		break;
	}
	return res;
}
void solve(){
	scanf("%d", &N);
	for(int i=1;i<=N;i++)scanf("%d", A+i);
	for(int i=1;i<=N;i++)deg[A[i]]++;
	queue <int> que;
	for(int i=1;i<=N;i++)if(deg[i] == 0)que.push(i);
	while(!que.empty()){
		int t = que.front(); que.pop();
		deg[A[t]]--;
		d[A[t]] = d[t] + 1;
		if(deg[A[t]] == 0){
			que.push(A[t]);
		}
	}
	for(int i=1;i<=N;i++)cyc[i] = deg[i], deg[i] = 0;
	for(int i=1;i<=N;i++)deg[A[i]]++;
	for(int i=1;i<=N;i++){
		if(deg[i] > 2 || (deg[i] == 2 && cyc[i] == 0)){
			printf("0");
			return;
		}
	}
	for(int i=1;i<=N;i++)p[i] = i, z[i] = 1;
	for(int i=1;i<=N;i++){
		int x = Find(i), y = Find(A[i]);
		if(x != y)p[x] = y, z[y] += z[x];
	}
	for(int i=1;i<=N;i++)if(deg[i] == 2)chk[Find(i)] = 1;
	for(int i=1;i<=N;i++)if(Find(i) == i && chk[i] == 0)OC[z[i]]++;
	ll ans = 1;
	for(auto e : OC){
		D[0] = 1;
		int t = ((e.Fi % 2 == 1 && e.Fi > 1) ? 2 : 1);
		for(int i=1;i<=e.Se;i++){
			D[i] = t * D[i-1] + (i > 1 ? ((ll)(i-1) * e.Fi % MOD) * D[i-2] : 0);
			D[i] %= MOD;
		}
		ans = ans * D[e.Se] % MOD;
	}
	for(int i=1;i<=N;i++)if(Find(i) == i && chk[i] == 1){
		ans = ans * get(i) % MOD;
	}
	printf("%lld\n", ans);
}

int main(){
	int Tc = 1; //scanf("%d", &Tc);
	for(int tc=1;tc<=Tc;tc++){
		solve();
	}
	return 0;
}