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<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN 100010
#define MOD 1000000007
typedef long long ll;
using namespace std;
int a[MAXN],pre[MAXN];
int d[MAXN],n,cnt[MAXN];
ll ans=1;
ll f[MAXN];
bool vis[MAXN];
int main(){
	SF("%d",&n);
	for(int i=1;i<=n;i++){
		SF("%d",&a[i]);
		d[a[i]]++;
	}
	for(int i=1;i<=n;i++){
		if(d[i]>2){
			PF("0");
			return 0;
		}
		if(d[i]<2||vis[i]==1)
			continue;
		int p=a[i];
		vis[i]=1;
		pre[p]=i;
		while(p!=i){
			if(vis[p]==1){
				PF("0");
				return 0;	
			}
			vis[p]=1;
			pre[a[p]]=p;
			p=a[p];	
		}
	}
	for(int i=1;i<=n;i++)
		if(d[i]==0){
			int p=i,l1=0,l2=1;
			while(vis[p]==0){
				vis[p]=1;
				p=a[p];
				l1++;
			}
			p=pre[p];
			while(d[p]!=2){
				p=pre[p];
				l2++;
			}
			if(l1<l2)
				ans=ans*2ll%MOD;
			else if(l1>l2){
				PF("0");
				return 0;
			}
		}
	for(int i=1;i<=n;i++)
		if(vis[i]==0){
			int len=0;
			int p=i;
			while(vis[p]==0){
				len++;
				vis[p]=1;
				p=a[p];
			}
			cnt[len]++;
		}
	for(int i=1;i<=n;i++){
		f[0]=1;
		ll mul=i%2+1;
		if(i==1)
			mul=1;
		f[1]=mul;
		for(int j=2;j<=cnt[i];j++)
			f[j]=(1ll*f[j-2]*(j-1)%MOD*i%MOD+f[j-1]*mul%MOD)%MOD;
		ans=ans*f[cnt[i]]%MOD;
	}
	PF("%lld",ans);
}