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<cstdio>
#include<cstring>
#include<algorithm>
#define boynextdoor return puts("0"),0
using namespace std;
const int N=100005,mod=1000000007;
int n,x,ans=1,ring[N],to[N],f[N],e[N][2];
char ch[5000005],*p=ch;
bool vis[N];
inline int rd(){
	register int res=0;
	while(*p<'0'||*p>'9'){
		p++;
	}
	while(*p>='0'&&*p<='9'){
		res=res*10+*p-'0';
		p++;
	}
	return res;
}
int main(){
	fread(ch,5000000,1,stdin);
	n=rd();
	for(int i=1;i<=n;i++){
		to[i]=rd();
		if(!e[to[i]][0]){
			e[to[i]][0]=i;
		}else if(!e[to[i]][1]){
			e[to[i]][1]=i;
		}else{
			boynextdoor;
		}
	}
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			int now=i,siz=0,last=0,prod=1;
			bool flag=false;
			while(!vis[now]){
				vis[now]=true;
				now=to[now];
			}
			int beg=now;
			do{
				siz++;
				if(e[to[now]][0]!=now){
					swap(e[to[now]][0],e[to[now]][1]);
				}
				now=to[now];
			}while(now!=beg);
			do{
				now=to[now];
				if(e[now][1]){
					flag=true;
					break;
				}
			}while(now!=beg);
			if(!flag){
				ring[siz]++;
				continue;
			}else{
				beg=now;
			}
			do{
				now=to[now];
				last++;
				if(e[now][1]){
					flag=true;
					int tmp=e[now][1],dep=0;
					while(tmp){
						dep++;
						vis[tmp]=true;
						if(e[tmp][1]){
							boynextdoor;
						}else{
							tmp=e[tmp][0];
						}
					}
					if(dep>last){
						boynextdoor;
					}else if(dep<last){
						prod=prod*2%mod;
					}
					last=0;
				}
			}while(now!=beg);
			ans=1LL*ans*prod%mod;
		}
	}
	for(int i=1;i<=n;i++){
		if(!ring[i]){
			continue;
		}
		int flag=(i&1)&&i!=1;
		f[0]=1,f[1]=flag+1;
		for(int j=2;j<=ring[i];j++){
			f[j]=(1LL*f[j-2]*(j-1)%mod*i+(f[j-1]<<flag))%mod;
		}
		ans=1LL*ans*f[ring[i]]%mod;
	}
	printf("%d\n",ans);
	return 0;
}