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 L long long
using namespace std;
const int q=1000000007;
int n,a[100010],b[100010],x[100010],f[100010],p=1,w[100010],u[100010];
vector<int> y[100010];
inline int C(int n,int m)
{
	return (L)a[n]*b[m/2]%q*b[n-m]%q;
}
inline void calc(int i)
{
	int j,k=0,l,v,e;
	for(j=i;w[j]<2;j=x[j])
	  {
	   w[j]=2;
	   u[++k]=j;
	  }
	if(j!=i || k==0)
	  return;
	for(i=2;i<k+2-i;i++)
	  swap(u[i],u[k+2-i]);
	u[k+1]=u[1];
	for(j=1,l=0,v=1;j<=k;j++,l--)
	  {
	   if(y[u[j]].size()>2)
	     v=0;
	   if(y[u[j]].size()==2)
	     {
		  if(l>0)
		    v=0;
		  if(l<0)
		    v=(v<<1)%q;
		  for(l=1,e=y[u[j]][0]^y[u[j]][1]^u[j+1];y[e].size()==1;e=y[e][0],l++);
		  if(y[e].size()>1)
		    v=0;
		 }
	  }
	if(l>0)
	  v=0;
	if(l<0)
	  v=(v<<1)%q;
	p=(L)p*v%q;
}
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	int i,j,k,l;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	  {
	   scanf("%d",&x[i]);
	   y[x[i]].push_back(i);
	  }
	b[1]=1;
	for(i=2;i<=n;i++)
	  b[i]=q-(L)q/i*b[q%i]%q;
	a[0]=b[0]=1;
	for(i=1;i<=n;i++)
	  {
	   a[i]=(L)a[i-1]*i%q;
	   b[i]=(L)b[i-1]*b[i]%q;
	  }
	for(i=1;i<=n;i++)
	  if(!w[i])
	    {
		 for(j=i,k=0,l=0;!w[j];j=x[j],k++)
		   {
		    w[j]=1;
		    if(y[j].size()>1)
		      l=1;
		   }
	     if(j==i)
	       {
			if(!l)
		      f[k]++;
		   }
		 else
		   calc(j);
		}
	for(i=1;i<=n;i++)
	  {
	   if(i&1 && i>1)
	     for(j=1,l=1;j<=f[i];j++)
	       l=(l<<1)%q;
	   else
	     l=1;
	   for(j=0,k=0;j*2<=f[i];j++,l=(L)l*i%q)
	     {
	      k=(k+(L)C(f[i],2*j)*l)%q;
	      l=(L)l*(q+1>>1)%q;
	      if(i&1 && i>1)
	        l=(L)l*(q+1>>1)%q*(q+1>>1)%q;
		 }
	   p=(L)p*k%q;
	  }
	printf("%d\n",p);
	return 0;
}