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 <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<iomanip>
#include<ctime>
#include<set>
#include<map>
#include<queue>
#include<stack>
#define sqr(x) ((x)*(x))
#define fz1(i,n) for ((i)=1;(i)<=(n);(i)++)
#define fd1(i,n) for ((i)=(n);(i)>=1;(i)--)
#define fz0g(i,n) for ((i)=0;(i)<=(n);(i)++)
#define fd0g(i,n) for ((i)=(n);(i)>=0;(i)--)
#define fz0k(i,n) for ((i)=0;(i)<(n);(i)++)
#define fd0k(i,n) for ((i)=(long long)((n)-1);(i)>=0;(i)--)
#define fz(i,x,y) for ((i)=(x);(i)<=(y);(i)++)
#define fd(i,y,x) for ((i)=(y);(i)>=(x);(i)--)
#define fzin fz1(i,n)
#define fzim fz1(i,m)
#define fzjn fz1(j,n)
#define fzjm fz1(j,m)
#define ff(c,itr) for (__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
#define rdst(st,len){static char ss[len];scanf(" %s",ss);(st)=ss;}
#define inc(x,y) {x+=(y);if(x>=mod)x-=mod;}
#define dec(x,y) {x-=(y);if(x<0)x+=mod;}
#define spln(i,n) (i==n?'\n':' ')
using namespace std;
int n,m,i,j,mod=1e9+7,vis[100005],icr[100005],a[100005],cnt[100005],ans,f[100005],g[100005];
vector<int> bi[100005];
vector<int> seq,nxt;
int qp(int x,int y)
{
	int z=1;
	while(y){
		if(y&1){
			z=1ll*z*x%mod;
		}
		y/=2;
		x=1ll*x*x%mod;
	}
	return z;
}
void solve(int x)
{
	int st=x;
	for(;;){
		int y=x,z,lst=0,l1=0,l2=0;
		for(;;){
			l1++;lst=y;y=a[y];vis[y]=1;
			if(bi[y].size()==2) break;
		}
		z=bi[y][0]^bi[y][1]^lst;vis[z]=1;
		l2=1;
		while(!bi[z].empty()){
			z=bi[z][0];l2++;vis[z]=1;
		}
		if(l2>l1){
			puts("0");
			exit(0);
		}
		if(l2<l1) ans=2ll*ans%mod;
		if(y==st) return;x=y;
	}
}
int main()
{
	scanf("%d",&n);
	fz1(i,n){
		scanf("%d",&a[i]);
		bi[a[i]].push_back(i);
	}
	fz1(i,n)if(!vis[i]){
		int x=i;while(!vis[x]){
			vis[x]=i;x=a[x];
		}
		if(vis[x]!=i) continue;
		while(!icr[x]){
			icr[x]=1;x=a[x];
		}
	}
	fz1(i,n){
		if(icr[i]){
			if(bi[i].size()>2){
				puts("0");
				return 0;
			}
		}
		else{
			if(bi[i].size()>1){
				puts("0");
				return 0;
			}
		}
	}
	ans=1;
	memset(vis,0,sizeof(vis));
	fz1(i,n)if(bi[i].size()==2&&!vis[i]){
		solve(i);
	}
	fz1(i,n)if(!vis[i]){
		int x=i,c=0;while(!vis[x]){
			vis[x]=1;x=a[x];c++;
		}
		cnt[c]++;
	}
	fz1(i,n){
		f[0]=1;if((i&1)&&i>1) f[1]=2; else f[1]=1;
		fz(j,2,cnt[i]){
			if((i&1)&&i>1) f[j]=(f[j-1]+f[j-1]+1ll*f[j-2]*(j-1)%mod*i)%mod; else f[j]=(f[j-1]+1ll*f[j-2]*(j-1)%mod*i)%mod;
		}
		ans=1ll*ans*f[cnt[i]]%mod;
	}
	cout<<ans<<endl;
	return 0;
}