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<vector>
#define N 100100
#define Q 1000000007
using namespace std;
bool vis[N];
int a[N],stk[N],cnt,num[N],cc,lf[N];
vector<int> cyc[N],g[N];
int dp[N];
int main(){
	int n,ans=1;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),g[a[i]].push_back(i);
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			int j;
			cnt=0;
			for(j=i;!vis[j];j=a[j]){
				vis[j]=true;
				stk[cnt++]=j;
			}
			do{
				cyc[cc].push_back(stk[--cnt]);
			}while(cnt&&stk[cnt]!=j);
			if(stk[cnt]==j) cc++;
			else cyc[cc].clear();
		}
	}
	for(int i=0;i<cc;i++){
		bool fx=false;
		for(int j=0;j<cyc[i].size();j++){
			int u=cyc[i][j];
			if(g[u].size()>2) ans=0;
			else if(g[u].size()==2){
				fx=true;
				lf[j]=0;
				int v=g[u][0]^g[u][1]^(cyc[i][(j+1)%cyc[i].size()]);
				while(1){
					lf[j]++;
					if(g[v].size()==1) v=g[v][0];
					else{
						if(g[v].size()>1) ans=0;
						break;
					}
				}
			}
			else lf[j]=0;
		}
		if(!fx) num[cyc[i].size()]++;
		else{
			for(int j=0;j<cyc[i].size();j++){
				if(lf[j]){
					for(int k=(j+1)%cyc[i].size();g[cyc[i][k]].size()==1;k=(k+1)%cyc[i].size()){
						lf[j]--;
					}
					if(lf[j]<=0) ans=(ans+ans)%Q;
					else if(lf[j]>1) ans=0;
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		dp[0]=1;
		dp[1]=1+(i>1)*(i&1);
		for(int j=2;j<=num[i];j++){
			dp[j]=(dp[1]*dp[j-1]+1LL*(j-1)*i%Q*dp[j-2])%Q;
		}
		ans=1LL*ans*dp[num[i]]%Q;
	}
	printf("%d\n",ans);
	return 0;
}