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 <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int MAXN=100010, LOG=20;

int n, m, k, u, v, x, y, t, a, b, ans=1;
int A[MAXN], B[MAXN], ted[MAXN], deg[MAXN];
int mark[MAXN], last[MAXN], dor[MAXN];
ll dp[MAXN];

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n;
	for (int i=1; i<=n; i++) cin>>A[i], deg[A[i]]++;
	for (int i=1; i<=n; i++) if (!mark[i]){
		int v=i;
		while (mark[v]<=2){
			if (last[v]!=i) last[v]=i, mark[v]=1;
			else mark[v]++;
			if (mark[v]==2) dor[v]=1;
			v=A[v];
		}
	}
	for (int i=1; i<=n; i++) if (deg[i]>2 || (deg[i]==2 && !dor[i])) kill(0);
	for (int i=1; i<=n; i++) B[A[i]]^=i;
	
	memset(mark, 0, sizeof(mark));
	for (int i=1; i<=n; i++) if (dor[i] && !mark[i]){
		int v=i, bad=0;
		while (!mark[v]){
			mark[v]++;
			B[A[v]]^=v;
			v=A[v];
		}
		vector<int> vec;
		while (mark[v]<2){
			mark[v]++;
			int len=0, u=v;
			while (!dor[B[u]] && B[u]){
				u=B[u];
				len++;
			}
			if (len) bad=1;
			vec.pb(len);
			v=A[v];
		}
//		debugv(vec)
		if (!bad){
			ted[vec.size()]++;
			continue ;
		}
		int c0=0;
		while (vec.back()==0) c0++, vec.pop_back();
		for (int x:vec){
			if (x==0) c0++;
			else{
				if (x<=c0) ans=ans*2%mod;
				if (x-1>c0) kill(0)
				c0=0; 
			}
		}
	}
//	debug(ans)
	for (int i=1; i<=n; i++) if (ted[i]){
		ll z=1+(i>1 && i%2);
		dp[0]=1;
		dp[1]=z;
		for (int j=2; j<=ted[i]; j++) dp[j]=(dp[j-1]*z + (j-1ll)*i%mod*dp[j-2])%mod;
		ans=ans*dp[ted[i]]%mod;
	}
	cout<<ans<<"\n";
	
	return 0;
}