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
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define fr(x) freopen(x,"r",stdin)
#define fw(x) freopen(x,"w",stdout)
#define iout(x) printf("%d\n",x)
#define lout(x) printf("%lld\n",x)
#define REP(x,l,u) for(int x = (l);x<=(u);x++)
#define RREP(x,l,u) for(int x = (l);x>=(u);x--)
#define mst(x,a) memset(x,a,sizeof(x))
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define MP make_pair
#define se second
#define fi first
#define dbg(x) cout<<#x<<" = "<<(x)<<endl;
#define sz(x) ((int)x.size())
#define cl(x) x.clear()

typedef  long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
using namespace std;

const int maxn = 100010;
const int mod = 1e9+7;
const int MAX = 1000000010;
const double eps = 1e-6;
const double PI = acos(-1);

template<typename T> inline void read(T &x){
x=0;T f=1;char ch;do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');do x=x*10+ch-'0',ch=getchar();while(ch<='9'&&ch>='0');x*=f;
}

template<typename A,typename B> inline void read(A&x,B&y){read(x);read(y);}
template<typename A,typename B,typename C> inline void read(A&x,B&y,C&z){read(x);read(y);read(z);}
template<typename A,typename B,typename C,typename D> inline void read(A&x,B&y,C&z,D&w){read(x);read(y);read(z);read(w);}
template<typename A,typename B> inline A fexp(A x,B p){A ans=1;for(;p;p>>=1,x=1LL*x*x%mod)if(p&1)ans=1LL*ans*x%mod;return ans;}
template<typename A,typename B> inline A fexp(A x,B p,A mo){A ans=1;for(;p;p>>=1,x=1LL*x*x%mo)if(p&1)ans=1LL*ans*x%mo;return ans;}

int n,ans=1;

int A[maxn],vi[maxn],Is[maxn],ch[maxn],has[maxn],f[maxn],deg[maxn];

int calc(int x,int y){
	if(x<y)return 2;
	if(x>y)return 0;
	return 1;
}

void Work(){
	REP(i,1,n)if(deg[i]>2||(deg[i]==2&&!Is[i]))return void(puts("0"));
	REP(i,1,n)if(!deg[i]){
		int x=i,t=0;while(!Is[x])x=A[x],t++;
		ch[x]=t;
	}
	REP(i,1,n)if(Is[i]){
		int x=i;
		do x=A[x];while(!ch[x]&&x!=i);
		if(x==i&&!ch[x]){
			int t=0;
			do x=A[x],t++,Is[x]=0;while(x!=i);
			has[t]++;
			continue;
		}
		
		int j=x,now=1;x=A[x];
		
		for(;;){
			if(ch[x]){
				ans=1ll*ans*calc(ch[x],now)%mod;
				now=0;
			}
			if(x==j)break;
			now++;x=A[x];
		}
		
		while(Is[x])Is[x]=0,x=A[x];
	}
	REP(i,1,n)if(has[i]){
		int x=(i>1&&(i&1))+1;
		f[0]=1;
		REP(j,1,has[i]){
			f[j]=1ll*f[j-1]*x%mod;
			if(j>=2)f[j]=(1ll*f[j-2]*(j-1)%mod*i+f[j])%mod;
		}
		ans=1ll*ans*f[has[i]]%mod;
	}
	iout(ans);
}

void Init(){
	read(n);
	REP(i,1,n)read(A[i]);
	REP(i,1,n)deg[A[i]]++;
	REP(i,1,n)if(!vi[i]){
		int x=i;
		while(!vi[x])vi[x]=i,x=A[x];
		if(vi[x]==i){
			while(!Is[x])Is[x]=1,x=A[x];
		}
	}
}

int main(){
	Init();
	Work();
	return 0;
}