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>
using namespace std;

const int MaxN=1e5+5;
const int Mod=1e9+7;

int N,Ans=1;
int A[MaxN],Deg[MaxN];
int Pre[MaxN],Cnt[MaxN],F[MaxN];
bool Vis[MaxN];

int main(){
	int i,j,l,l1,l2;
	scanf("%d",&N);
	for(i=1;i<=N;i++)
		scanf("%d",&A[i]),Deg[A[i]]++;
	for(i=1;i<=N;i++){
		if(Deg[i]>2){
			puts("0");
			return 0;
		}
		if(Deg[i]<2||Vis[i])
			continue;
		j=i;
		do{
			if(Vis[j]){
				puts("0");
				return 0;
			}
			Vis[j]=true;
			Pre[A[j]]=j;
			j=A[j];
		}while(i^j);
	}
	for(i=1;i<=N;i++)
		if(!Deg[i]){
			l1=l2=0;
			for(j=i;!Vis[j];j=A[j])
				Vis[j]=true,l1++;
			do j=Pre[j],l2++;
			while(Deg[j]==1);
			if(l1>l2){
				puts("0");
				return 0;
			}
			if(l1<l2)
				Ans=2*Ans%Mod;
		}
	for(i=1;i<=N;i++)
		if(!Vis[i]){
			l=0;
			for(j=i;!Vis[j];j=A[j])
				Vis[j]=true,l++;
			Cnt[l]++;
		}
	for(i=1;i<=N;i++){
		l=((i&1)&&i>1)+1;
		F[0]=1,F[1]=l;
		for(j=2;j<=Cnt[i];j++)
			F[j]=(1ll*F[j-2]*(j-1)*i+F[j-1]*l)%Mod;
		Ans=1ll*Ans*F[Cnt[i]]%Mod;
	}
	printf("%d\n",Ans);
	return 0;
}