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;
#define Set(a,b) memset(a,b,sizeof(a))
typedef long long ll;
const int N=1e5+10;
const int mod=1e9+7;
int fa[N],n,son[N],len[N];
bool cir[N];int vis[N];
int num[N];int dp[N];
template<class T>inline void Inc(T&x,int y){x+=y;if(x>=mod) x-=mod;return;}
inline int Mod(int x){if(x>=mod) x-=mod;return x;}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i) scanf("%d",&fa[i]),++son[fa[i]];
	for(int i=1;i<=n;++i) {
		if(vis[i]) continue;
		int u=i;
		while(!vis[u]) vis[u]=i,u=fa[u];
		if(vis[u]==i) {while(!cir[u]) cir[u]=1,u=fa[u];}
	}
	for(int i=1;i<=n;++i) if((cir[i]&&son[i]>2)||(!cir[i]&&son[i]>1)) return puts("0"),0;
	for(int i=1;i<=n;++i) {
		if(!son[i]) {
			int u=i,l=0;
			while(!cir[u]) ++l,u=fa[u];
			if(len[u]) return puts("0"),0;
			len[u]=l;
		}
	}int ans=1;
	for(int i=1;i<=n;++i){
		if(!cir[i]) continue;
		int size=0,fir=0,pfir=0,now=0;
		for(int u=i;cir[u];u=fa[u]){
			++size;cir[u]=0;
			if(len[u]) {
				if(!fir) fir=size,pfir=u,now=size;
				else {
					int pre=now;now=size;int d=now-pre;
					if(d>len[u]) Inc(ans,ans);
					else if(d<len[u]) {puts("0");return 0;}
				}
			}
		}
		if(!fir) ++num[size];
		else {
			int d=size-now+fir;
			if(d>len[pfir]) Inc(ans,ans);
			else if(d<len[pfir]) {puts("0");return 0;}
		}
	}
	for(int i=1;i<=n;++i){
		if(!num[i]) continue;dp[0]=1;
		for(int j=1;j<=num[i];++j) {
			dp[j]=dp[j-1];//keep the same
			if(i>1&&(i&1)) Inc(dp[j],dp[j]);//two kinds
			if(j>1) Inc(dp[j],(ll)dp[j-2]*(j-1)%mod*i%mod);// union
		}
		ans=(ll)ans*dp[num[i]]%mod;
	}
	printf("%d\n",ans%mod);
}