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 int long long
const int N=100005,M=1e9+7; 
int n,a[N],pre[N],deg[N],cnt[N],f[N],ans=1,vis[N];
signed main(){
	scanf("%lld",&n);
	for (int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		deg[a[i]]++;
	}
	for (int i=1;i<=n;i++){
		if (deg[i]>2){
			printf("0\n");
			return 0;
		}
		if (deg[i]<2||vis[i])continue;
		int p=i;
		while (p!=i||!vis[p]){
			if (vis[p]){
				printf("0\n");
				return 0;
			}
			vis[p]=1;
			pre[a[p]]=p;
			p=a[p];
		}
	}
	for (int i=1;i<=n;i++)
		if (!deg[i]){
			int p=i,l1=0,l2=0;
			while (!vis[p])vis[p]=1,p=a[p],l1++;
			do {
				l2++;
				p=pre[p];
			}while(deg[p]!=2);
			if (l1<l2)ans=ans*2%M;
			else if (l1>l2){
				printf("0\n");
				return 0;
			}
		}
	for (int i=1;i<=n;i++)
		if (!vis[i]){
			int p=i,l=0;
			do {
				l++;
				p=a[p];
				vis[p]=1;
			}
			while(p!=i);
			cnt[l]++;
		}
	for (int i=1;i<=n;i++){
		int mul=1;
		if (i!=1&&(i&1))mul++;
		f[0]=1;f[1]=mul;
		for (int j=2;j<=cnt[i];j++)
			f[j]=(f[j-2]*(j-1)%M*i+f[j-1]*mul)%M;
		ans=ans*f[cnt[i]]%M;
	}
	printf("%lld\n",ans);
}