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 N=100100,mod=1000000007;
typedef long long ll;
int a[N],d[N],n,vis[N],ans=1,cnt[N],b[N];
void gofail(){cout<<0<<'\n';exit(0);}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;++i)cin>>a[i],d[a[i]]++;//,b[a[i]]=i;
	for(int i=1;i<=n;++i){
		if(d[i]>2)gofail();
		if(d[i]<2||vis[i])continue;
		vis[i]=1;b[a[i]]=i;
		for(int j=a[i];j!=i;j=a[j]){
			if(vis[j])gofail();
			vis[j]=1;b[a[j]]=j;
		}
	}
	for(int i=1;i<=n;++i)
		if(!d[i]){
			int cha=0,cir=1,j=i;
			for(;!vis[j];j=a[j])vis[j]=1,++cha;
			for(j=b[j];d[j]<2;j=b[j])++cir;
			if(cha<cir)ans=ans*2%mod;
			else if(cha>cir)gofail();
		}
	for(int i=1;i<=n;++i)
		if(!vis[i]){
			int L=1;vis[i]=1;
			for(int j=a[i];j!=i;j=a[j])vis[j]=1,++L;
			cnt[L]++;
		}
	for(int i=1;i<=n;++i)if(cnt[i]){
		int t=2;if(i==1||(i%2==0))t=1;
		int u=1,v=t;
		for(int j=2;j<=cnt[i];++j){
			int w=((ll)u*(j-1)%mod*i+(ll)v*t)%mod;
			u=v;v=w;
		}
		ans=(ll)ans*v%mod;
	}
	cout<<ans<<'\n';
	return 0;
}