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 N 1111116
#define mod 1000000007

int n,a[N],d[N],h[N],g[N];
long long ans,f[N];
queue<int> q;

int read(){
	int x=0,f=1;char ch=getchar();
	for (;!isdigit(ch);ch=getchar()) if (ch=='-')  f=-f;
	for (;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
	return x*f;
}

int main(){
	n=read();ans=1;
	for (int i=1;i<=n;i++) a[i]=read(),d[a[i]]++;
	for (int i=1;i<=n;i++) if (!d[i]) q.push(i);
	while (!q.empty()){
		int t=q.front();q.pop();
		if (h[a[t]]) ans=0;h[a[t]]=h[t]+1;
		if (--d[a[t]]==0) q.push(a[t]);
	}
	for (int i=1;i<=n;i++)
		if (d[i]){
			int t=i;vector<int> q;
			while (a[t]!=i&&!h[t]) t=a[t];
			while (d[t]){
				q.push_back(h[t]);
				d[t]=0;t=a[t];
			}
			if (!q[0]) g[q.size()]++;
			else {
				q.push_back(q[0]);
				for (int i=1,j=0;i<(int)q.size();i++)
					if (q[i]){
						if (q[i]<i-j) ans=ans*2%mod;
						if (q[i]>i-j) ans=0;
						j=i;
					}
			}
		}
	for (int i=1;i<=n;i++){
		f[0]=1;f[1]=(i>1&&i%2)+1;
		for (int j=2;j<=g[i];j++)
			f[j]=(f[j-1]*f[1]+f[j-2]*(j-1)*i)%mod;
		ans=(ans*f[g[i]])%mod;
	}
	printf("%lld\n",ans);return 0;
}