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>
const int mod=1e9+7;
using namespace std;
int n,du[100010],vis[100010],nxt[100010],L[100010],ans=1,cir_len[100010],f[100010];
bool cir[100010];
void work_cir(int u){
	int now=0,pre=0,f_pos=0,f_L=0;
	while(cir[u]){
		cir[u]=false,now++;
		if(L[u]){
			if(!f_pos) f_pos=pre=now,f_L=L[u];
			else{
				int k=(L[u]<now-pre)+(L[u]<=now-pre);
				ans=1ll*ans*k%mod,pre=now;
			}
		}
		u=nxt[u];
	}
	if(!f_pos) ++cir_len[now];
	else{
		int k=(f_L<now-pre+f_pos)+(f_L<=now-pre+f_pos);
		ans=1ll*ans*k%mod;
	}
}
int main(){ 
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&nxt[i]),++du[nxt[i]];
	for(int i=1;i<=n;i++){
		if(vis[i]) continue;
		int now=i;
		while(!vis[now]) vis[now]=i,now=nxt[now];
		if(vis[now]!=i) continue;
		while(!cir[now]) cir[now]=true,now=nxt[now];
	}
	for(int i=1;i<=n;i++){
		if((cir[i]&&du[i]>2)||(!cir[i]&&du[i]>1)){
			puts("0\n");
			return 0;
		}
	}
	for(int i=1;i<=n;i++){
		if(du[i]) continue;
		int now=i,len=0;
		while(!cir[now]) ++len,now=nxt[now];
		L[now]=len;
	}
	for(int i=1;i<=n;i++) if(cir[i]) work_cir(i);
	for(int i=1;i<=n;i++){
		if(!cir_len[i]) continue;
		f[0]=1;
		for(int j=1;j<=cir_len[i];j++){
			if(i>1&&(i&1)) f[j]=(2ll*f[j-1])%mod;
			else f[j]=f[j-1];
			if(j>1) f[j]=(f[j]+(1ll*f[j-2]*(j-1)%mod)*i%mod)%mod;
		}
		ans=1ll*ans*f[cir_len[i]]%mod;
	}
	printf("%d\n",ans);
}