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>
#define ll long long
#define ull unsigned ll
#define uint unsigned
#define db long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define IT iterator

#define PB push_back
#define MK make_pair
#define LB lower_bound
#define UB upper_bound
#define EB emplace_back
#define fi first
#define se second

#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define UPD(x,y) (((x)+=(y))>=mo?x-=mo:233)
#define CLR(a,v) memset(a,v,sizeof(a));
#define CPY(a,b) memcpy(a,b,sizeof(a));

#define LS3 k*2,l,mid
#define RS3 k*2+1,mid+1,r
#define LS5 k*2,l,mid,x,y
#define RS5 k*2+1,mid+1,r,x,y
#define GET pushdown(k);int mid=(l+r)/2

#define INF ((1ll<<60)-233)
#define sqr(x) ((x)*(x))
#define debug puts("wzpkking")
using namespace std;
const int N=100005;
const int mo=1000000007;
int n,ans=1;
int a[N],deg[N];
int pre[N],cnt[N],f[N];
bool vis[N];
int main(){
	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 (deg[i]>2) return puts("0"),0;
		if (deg[i]<2||vis[i]) continue;
		int j=i;
		do{
			if (vis[j]) return puts("0"),0;
			vis[j]=1; pre[a[j]]=j; j=a[j];
		}while (i!=j);
	}
	for (int i=1;i<=n;i++) if (!deg[i]){
		int l1=0,l2=0,j=i;
		for (;!vis[j];j=a[j]) vis[j]=1,l1++;
		for (j=pre[j],l2++;deg[j]==1;j=pre[j],l2++);
		if (l1>l2) return puts("0"),0;
		if (l1<l2) ans=1ll*ans*2%mo;
	}
	for (int i=1;i<=n;i++) if (!vis[i]){
		int l=0;
		for (int j=i;!vis[j];j=a[j])
			vis[j]=1,l++;
		cnt[l]++;
	}
	for (int i=1;i<=n;i++){
		int l=((i&1)&&(i>1))+1;
		f[0]=1; f[1]=l;
		for (int j=2;j<=cnt[i];j++)
			f[j]=(1ll*f[j-2]*(j-1)*i+1ll*f[j-1]*l)%mo;
		ans=1ll*ans*f[cnt[i]]%mo;
	}
	printf("%d\n",ans);
}