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;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define mp make_pair
#define PI pair<int,int>
#define lowbit(i) i&-i
#define For(i,l,r) for(int i=(int)(l);i<=(int)(r);i++)
#define Rep(i,r,l) for(int i=(int)(r);i>=(int)(l);i--)
#define pb push_back
#define fi first
#define se second
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline ll read(){
	ll x = 0; char ch = gc(); bool positive = 1;
	for (; !isdigit(ch); ch = gc())	if (ch == '-')	positive = 0;
	for (; isdigit(ch); ch = gc())	x = x * 10 + ch - '0';
	return positive ? x : -x;
}
inline void write(ll a){
    if(a<0){
    	a=-a; putchar('-');
	}
    if(a>=10)write(a/10);
    putchar('0'+a%10);
}
inline void writeln(ll a){write(a); puts("");}
inline void wri(ll a){write(a); putchar(' ');}
inline ull rnd(){
	ull ans=0; For(i,0,5)ans=ans<<15^rand(); return ans;
}
const int N=100005,mod=1000000007;
int a[N],f[N],fa[N],TO[N];
vector<int> pre[N],v[N];
ll fac[N],ni[N],ans=1;
bool vis[N];
inline int gf(int x){
	return fa[x]==x?x:fa[x]=gf(fa[x]);
}
void GG(int frog){
	if(!frog){
		puts("0"); exit(0);
	}
}
int getpre(int x,int id){
	For(i,0,1)if(vis[pre[x][i]]==id)return pre[x][i];
	assert(0);
}
ll ksm(ll a,int b){
	int ans=1;
	for(;b;b>>=1){
		if(b&1)ans=ans*a%mod;
		a=a*a%mod;
	}
	return ans;
}
void mer(int x,int y){
	fa[gf(x)]=gf(y);
}
int main(){
	int n=read();
	For(i,fac[0]=1,n)fac[i]=fac[i-1]*i%mod;
	ni[n]=ksm(fac[n],mod-2); Rep(i,n,1)ni[i-1]=ni[i]*i%mod;
	For(i,1,n)pre[a[fa[i]=i]=read()].pb(i);
	For(i,1,n)mer(i,a[i]);
	For(i,1,n)v[gf(i)].pb(i);
	For(i,1,n)if(fa[i]==i){
		int f=1;
		for(auto j:v[i])if(pre[j].size()!=1)f=0;
		if(f)TO[v[i].size()]++;
		else{
			for(int j=i;;j=a[j]){
				if(!vis[j])vis[j]=1;
				else{
					for(auto k:v[i])vis[k]=0;
					vis[j]=1; for(int k=a[j];k!=j;k=a[k])vis[k]=1;
					bool t=0; int sz=0;
					for(int k=j;t==0||k!=j;k=a[k]){
						t=1;
						int f=0,g=0;
						if(pre[k].size()>=2){//cout<<pre[k].size()<<endl;
							GG(pre[k].size()==2);
							for(int l=getpre(k,1);pre[l].size()==1;l=pre[l][0])f++;
							for(int l=getpre(k,0);pre[l].size();l=pre[l][0]){GG(pre[l].size()==1);g++;}
							g++;
							//cout<<g<<" "<<f<<endl;
							GG(g<=f+1);
							if(g<=f)ans=ans*2%mod; 
							//cout<<g<<" "<<f<<" "<<v[k].size()<<endl;
						}
					}
					break;
				}
			}
		}
	}
	For(i,1,n)if(TO[i]){
		int d=((i&1)&&i>1)?2:1;
		int sum=ksm(d,TO[i]);
		For(j,1,TO[i]/2)sum=(sum+fac[TO[i]]*ni[j]%mod*ni[TO[i]-j-j]%mod*ksm(d,TO[i]-j-j)%mod*ksm((ll)i*(mod+1)/2%mod,j))%mod;
		//cout<<sum<<" "<<TO[i]<<endl;
		ans=ans*sum%mod;
	}
	cout<<ans<<endl;
}