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>
#define pb push_back

using namespace std;

const int N=100005,P=1e9+7;
typedef long long ll;

int n,ans=1,crc[N],nx[N],f0,f1,f2;
vector<int>e[N];
bool vis[N],in[N];

inline void Assert(bool f){if(!f)puts("0"),exit(0);}
int find(int x){if(in[x])return x;in[x]=true;int R=find(nx[x]);return in[x]=false,R;}
int dfs(int x){vis[x]=true;Assert(e[x].size()<=1);for(int v:e[x])return dfs(v)+1;return 1;}

void check(int x){
	int u=find(x),m=1;
	static vector<int>cr,le;
	cr.clear();cr.pb(u);in[u]=vis[u]=true;
	for(int p=nx[u];p!=u;p=nx[p])cr.pb(p),in[p]=vis[p]=true,m++;
	le.resize(cr.size());
	int f=-1;
	for(int i=0,v;i<m;i++){
		Assert(e[v=cr[i]].size()<=2);
		for(int p:e[v])if(!in[p])le[i]=dfs(p),f=i;
		if(e[v].size()==1)le[i]=0;
	}
	if(f==-1){crc[m]++;return;}
	for(int i=0;i<m;i++){
		if(le[i]){
			int dis=(i-f+m)%m;
			if(f==i)dis=m;
			Assert(dis>=le[i]);
			if(dis>le[i])ans=(ans<<1)%P;
			f=i;
		}
	}
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&nx[i]),e[nx[i]].pb(i);
	for(int i=1;i<=n;i++)if(!vis[i])check(i);
	for(int i=1;i<=n;i++)if(crc[i]){
		int c0=1+(i%2==1&&i>=3);
		f0=1,f1=c0;
		for(int j=2;j<=crc[i];j++){
			f2=((ll)(j*i-i)*f0%P+c0*f1)%P;
			f0=f1,f1=f2;
		}
		ans=(ll)ans*f1%P;
	}
	printf("%d\n",ans);
	return 0;
}