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 long long ll;
const int N=2e5+10,p=1e9+7;
int inc(int x,int y){x+=y;return x>=p?x-p:x;}
int mul(int x,int y){return (ll)x*y%p;}
int n,a[N],cir[N],link[N],len[N],top[N];
bool ok[N];
int length(int x){
	if (top[x]) return link[x];
	link[x]=length(a[x])+1;
	top[x]=top[a[x]];
	return link[x];
}
int cnt[N];
void init(){
	static int vis[N],deg[N];
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]),deg[a[i]]++;
	for (int i=1;i<=n;i++)
	if (!vis[i]){
		int j=i;
		while (!vis[j]) vis[j]=i,j=a[j];
		if (vis[j]!=i) continue;
		int p=j;
		for (cir[p]=p,j=a[j];j!=p;cir[j]=p,j=a[j]);
	}
	for (int i=1;i<=n;i++)
		if (cir[i]) len[cir[i]]++,top[i]=i;
	for (int i=1;i<=n;i++) length(i);
	for (int i=1;i<=n;i++){
		if (deg[i]>2) puts("0"),exit(0);
		if (deg[i]>1&&!cir[i]) puts("0"),exit(0);
	}
	for (int i=1;i<=n;i++) link[top[i]]=max(link[top[i]],link[i]);
	for (int i=1;i<=n;i++)
		if (link[i]) ok[cir[top[i]]]=1;
	for (int i=1;i<=n;i++)
		if (!ok[i]&&len[i]) cnt[len[i]]++;
}
typedef pair<int,int> pii;
int calc(int L,int n){
	static map<pii,int> M;
	if (!n) return 1;
	pii now(L,n);
	if (M.count(now)) return M[now];
	int ans=calc(L,n-1);
	if ((L&1)&&L>1) ans=inc(ans,ans);
	if (n>1) ans=inc(ans,mul(mul(L,(n-1)),calc(L,n-2)));
	return M[now]=ans;
}
int q[N],size;
int Calc(){
	static int cnt[N];
	for (int i=0;i<=size*2;i++) cnt[i]=0;
	for (int i=1;i<=size;i++)
		if (q[i]>size) return 0;
	for (int i=1;i<=size;i++) cnt[size+i-q[i]]++,cnt[size+i]--;
	for (int i=1;i<=size*2;i++) cnt[i]+=cnt[i-1];
	for (int i=1;i<=size;i++) cnt[i]=cnt[i+size]=cnt[i]+cnt[i+size];
	cnt[0]=cnt[size];
	for (int i=1;i<=size;i++)
		if (cnt[i]>1) return 0;
	int ans=1;
	for (int i=1;i<=size;i++)
		if (q[i]&&!cnt[size+i-q[i]-1]) ans=inc(ans,ans);
	return ans;
}
int main()
{
	init();
	int ans=1;
	for (int i=1;i<=n;i++)
		if (cnt[i]) ans=mul(ans,calc(i,cnt[i]));
	for (int i=1;i<=n;i++)
	if (ok[i]&&len[i]){
		q[size=1]=link[i];
		for (int j=a[i];j!=i;j=a[j]) q[++size]=link[j];
		ans=mul(ans,Calc());
	}
	printf("%d\n",ans);
	return 0;
}