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 double db;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pa;
typedef unsigned int uint;
typedef unsigned long long ull;
#define w1 first
#define ls (x<<1)
#define w2 second
#define rs (x<<1|1)
#define mp make_pair
#define pb push_back
#define mid ((l+r)>>1)
#define SZ(x) (int((x).size()))
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define rep2(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define per(i,a,b) for(int (i)=(a);(i)>=(b);(i)--)
#define Rep(p,x) for(int (p)=head[(x)];(p);(p)=nxt[(p)])
#define Rep2(p,x) for(int (p)=cur[(x)];(p);(p)=nxt[(p)])
template<class T>void read(T&num){
	num=0;T f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();
	num*=f;
}
const int maxn=1e5+5,mod=1e9+7;
int n,ans=1;
int a[maxn],d[maxn],vis[maxn],len[maxn],q[maxn],cnt[maxn],f[maxn];
void solve(int n,int m){
	int now=1+(n>1&&(n&1));
	f[0]=1;
	f[1]=now;
	rep(i,2,m)f[i]=(1ll*now*f[i-1]%mod+1ll*(i-1)*n%mod*f[i-2]%mod)%mod;
	ans=1ll*ans*f[m]%mod;
}
int main(){
	read(n);
	rep(i,1,n)read(a[i]),d[a[i]]++;
	rep(i,1,n)if(d[i]>2)ans=0;
	rep(i,1,n)if(!d[i]){
		int j=i,l=0;
		for(;d[j]<2;j=a[j],l++)vis[j]=1;
		len[j]=l;
	}
	rep(i,1,n)if(!vis[i]){
		int tot=0,j;
		for(j=i;!vis[j];j=a[j])vis[j]=1,q[++tot]=j;
		if(j!=i)ans=0;
		int cir=1;
		rep(j,1,tot)if(len[q[j]])cir=0;
		if(cir)cnt[tot]++;
		else{
			int maxl=1;
			per(j,tot,1)
				if(!len[q[j]])maxl++;
				else break;
			rep(j,1,tot)
				if(len[q[j]]){
					if(len[q[j]]<maxl)ans=2ll*ans%mod;
					if(len[q[j]]>maxl)ans=0;
					maxl=1;
				}else maxl++;
		}
	}
	rep(i,1,n)if(cnt[i])solve(i,cnt[i]);
	printf("%d\n",ans);
	return 0;
}