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<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e5;
const int mod=1e9+7;
int n,cnt,ans=1;
int a[maxn+8],deg[maxn+8],vis[maxn+8],cir[maxn+8],l1[maxn+8],l2[maxn+8],sum[maxn+8];
int f[maxn+8];
bool tree[maxn+8];

int read()
{
    int x=0,f=1;char ch=getchar();
    for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
    for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
    return x*f;
}

void solve(int x)
{
    int siz_line=0;
    while(!cir[x]) siz_line++,x=a[x];
    l1[x]=siz_line;
    tree[cir[x]]=1;
    siz_line=1,x=a[x];
    while(deg[x]!=2) siz_line++,x=a[x];
    l2[x]=siz_line;
}

int main()
{
    n=read();
    for (int i=1;i<=n;i++) a[i]=read(),deg[a[i]]++;
    for (int i=1;i<=n;i++)
	{
	    if (vis[i]) continue;
	    int x=i;
	    while(!vis[x]) vis[x]=i,x=a[x];
	    if (vis[x]!=i) continue;
	    ++cnt;
	    while(!cir[x]) cir[x]=cnt,x=a[x];
	}
    memset(vis,0,sizeof(vis));
    for (int i=1;i<=n;i++) if (deg[i]>(1+(cir[i]>0))) {puts("0");return 0;}
    for (int i=1;i<=n;i++) if (!deg[i]) solve(i);
    for (int i=1;i<=n;i++)
	if (l1[i]) ans=1ll*ans*((l2[i]>=l1[i])+(l2[i]>l1[i]))%mod;
    for (int i=1;i<=n;i++)
	{
	    if (!cir[i]) continue;
	    if (tree[cir[i]]) continue;
	    if (vis[i]) continue;
	    int x=i,siz=0;while(!vis[x]) siz++,vis[x]=1,x=a[x];
	    sum[siz]++;
	}
    for (int i=1;i<=n;i++)
	{
	    if (!sum[i]) continue;
	    //printf("%d %d\n",i,sum[i]);
	    f[0]=1;
	    for (int j=1;j<=sum[i];j++)
		{
		    f[j]=f[j-1];
		    if (i>1&&(i&1)) f[j]=(f[j]+f[j-1])%mod;
		    if (j>1) f[j]=(f[j]+1ll*f[j-2]*(j-1)%mod*i%mod)%mod;
		}
	    ans=1ll*ans*f[sum[i]]%mod;
	}
    printf("%d\n",ans);
    return 0;
}