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<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<bitset>
#include<map>

#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define fi first
#define se second

using namespace std;

typedef long long LL;
typedef double db;

int get(){
	char ch;
	while(ch=getchar(),(ch<'0'||ch>'9')&&ch!='-');
	if (ch=='-'){
		int s=0;
		while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
		return -s;
	}
	int s=ch-'0';
	while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
	return s;
}

const int N = 2e+5+5;
const int mo = 1e+9+7;

int cnt[N];
LL inv[N],js[N],miv[N];
int n;
int a[N];
int fa[N];
struct edge{
	int x,nxt;
}e[N*2];
int h[N],tot,key[N],k;
bool bz[N];
int pt[N],u;
int siz[N];
int pre[N],suf[N];

bool dfs(int x){
	bz[x]=1;
	siz[x]=1;
	int s=0;
	for(int p=h[x];p;p=e[p].nxt)
	if (!bz[e[p].x]){
		s++;
		if (dfs(e[p].x))return 1;
		siz[x]+=siz[e[p].x];
	}
	return s>1;
}

LL quickmi(LL x,LL tim){LL ans=1;for(;tim;tim/=2,x=x*x%mo)if (tim&1)ans=ans*x%mo;return ans;}

int getfather(int x){return fa[x]==x?x:fa[x]=getfather(fa[x]);}

void inse(int x,int y){
	e[++tot].x=y;
	e[tot].nxt=h[x];
	h[x]=tot;
}

int main(){
	n=get();
	inv[0]=js[0]=inv[1]=js[1]=miv[0]=1;
	miv[1]=(mo+1)/2;
	fo(i,2,n){
		inv[i]=1ll*(mo-mo/i)*inv[mo%i]%mo;
		js[i]=js[i-1]*i%mo;
		miv[i]=miv[i-1]*miv[1]%mo;
	}
	fo(i,2,n)inv[i]=inv[i]*inv[i-1]%mo;
	fo(i,1,n)fa[i]=i;
	fo(i,1,n){
		int x=a[i]=get();
		inse(x,i);
		int tx=getfather(x),ti=getfather(i);
		if (tx!=ti)fa[ti]=tx;
		else key[++k]=i;
	}
	int ans=1;
	fo(i,1,k){
		int x=key[i];
		bz[pt[u=1]=x]=1;
		for(x=a[x];x!=key[i];x=a[x])bz[pt[++u]=x]=1;
		fo(j,1,u)if (dfs(pt[j])){ans=0;break;}if (!ans)break;
		int ps=0;
		fd(j,u,1){ps=max(0,ps-1);if (siz[pt[j]]>1){if (ps){ans=0;break;}ps=siz[pt[j]]-1;}}if (!ans)break;
		fd(j,u,1){ps=max(0,ps-1);if (siz[pt[j]]>1){if (ps){ans=0;break;}ps=siz[pt[j]]-1;}}if (!ans)break;
		int mx=0;
		fo(j,1,u)mx=max(mx,siz[pt[j]]);
		if (mx==1)cnt[u]++;
		fo(j,1,u)pre[j]=pre[j-1]+siz[pt[j]]-1;
		fo(j,1,u)pre[j+u]=pre[j+u-1]+siz[pt[j]]-1;
		fo(j,1,u)
		if (siz[pt[j]]>1){
			if (pre[j+u-1]==pre[j+u-siz[pt[j]]])ans=ans*2%mo;
		}
	}
	if (!ans)return printf("0\n"),0;
	fo(i,1,n)
	if (cnt[i]){
		LL now=1,tmp=0;
		fo(j,0,cnt[i]/2){
			if (i%2==1&&i>1)tmp=(tmp+js[cnt[i]]*inv[j]%mo*inv[cnt[i]-j*2]%mo*miv[j]%mo*now%mo*quickmi(2,cnt[i]-j*2)%mo)%mo;
			else tmp=(tmp+js[cnt[i]]*inv[j]%mo*inv[cnt[i]-j*2]%mo*miv[j]%mo*now%mo)%mo;
			now=now*i%mo;
		}
		ans=tmp*ans%mo;
	}
	printf("%d\n",ans);
	return 0;
}