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 N 200010
#define ll long long
#define mod 1000000007
using namespace std;

struct edge{int x, y, next;}a[N];
int n, p[N], x, l, flag[N], sum, s[N], cl, d[N], fa[N], ans, def[N], f[N], ff, last, g[N];

inline void add(int x, int y){a[++l].x=x; a[l].y=y; a[l].next=p[x]; p[x]=l;}

inline void dfs(int x, int FA){
	flag[x]=1; sum++;
	for(int i=p[x]; i; i=a[i].next)if(i!=(FA^1)){
		if(flag[a[i].y]){cl=1; d[0]=x; d[1]=a[i].y;}
		else{fa[a[i].y]=x; dfs(a[i].y, i);}
	}
}

inline void dfs1(int x, int fa){
	def[x]=0;
	int sum=0;
	for(int i=p[x]; i; i=a[i].next)if(fa!=a[i].y&&!f[a[i].y]){
		sum++; dfs1(a[i].y, x); def[x]=def[a[i].y]+1;
	}
	if(sum>=2)ff=0;
}

int main(){
	scanf("%d", &n);
	l=1; memset(p, 0, sizeof(p));
	for(int i=1; i<=n; i++){scanf("%d", &x); add(x, i); add(i, x);}
	ans=1; memset(flag, 0, sizeof(flag)); memset(s, 0, sizeof(s)); memset(f, 0, sizeof(f));
	for(int i=1; i<=n; i++)if(!flag[i]){
		sum=0; dfs(i, 0);
		x=d[1]; while(x!=d[0]){x=fa[x]; d[++cl]=x;}
		if(sum==cl){s[sum]++; continue;}
		for(int j=p[d[1]]; j; j=a[j].next)if(a[j].y==d[0])
			if(j&1){for(int k=1; k<=cl/2; k++)swap(d[k], d[cl-k+1]); d[0]=d[cl];}
		for(int j=1; j<=cl; j++)f[d[j]]=1;
		ff=1;
		for(int j=1; j<=cl&&ff; j++)dfs1(d[j], 0);
		if(!ff){printf("0"); return 0;}
		last=cl; while(!def[d[last]])last--;
		for(int j=1; j<=cl; j++)if(def[d[j]]){
			x=(j-last-1+cl)%cl;
			if(def[d[j]]<=x)ans=ans*2%mod;
			if(def[d[j]]>=x+2){printf("0"); return 0;}
			last=j;
		}
	}
	for(int i=1; i<=n; i++)if(s[i]){
		x=1; if((i&1)&&i>=3)x++;
		g[0]=1; g[1]=x;
		for(int j=2; j<=s[i]; j++)g[j]=((ll)x*g[j-1]%mod+(ll)(j-1)*i%mod*g[j-2]%mod)%mod;
		ans=(ll)ans*g[s[i]]%mod;
	}
	printf("%d", ans);
	return 0;
}