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<cctype>
const int N=100007,P=1000000007;
int a[N],deg[N],vis[N],pre[N],cnt[N],f[N];
int read(){int x=0,c=getchar();while(isspace(c))c=getchar();while(isdigit(c))(x*=10)+=c&15,c=getchar();return x;}
int add(int a,int b){return a+=b-P,a+(a>>31&P);}
int mul(int a,int b){return 1ll*a*b%P;}
int main()
{
    int n=read(),ans=1;
    for(int i=1;i<=n;++i) ++deg[a[i]=read()];
    for(int i=1;i<=n;++i)
    {
	if(deg[i]>2) return puts("0"),0;
	if(deg[i]<2||vis[i]) continue;
	//for(int p=i;!vis[p];vis[p]=1,pre[a[p]]=p,p=a[p]) if(vis[p]) return puts("0"),0;
	int p=i;
	do
	{
	    if(vis[p]) { printf("0\n"); return 0; }
	    vis[p]=1,pre[a[p]]=p,p=a[p];
	}while(p!=i);
    }
    for(int i=1,p,l1,l2;i<=n;++i)
	if(!deg[i])
	{
	    for(p=i,l1=0,l2=0;!vis[p];p=a[p]) vis[p]=1,++l1;
	    do ++l2,p=pre[p]; while(deg[p]^2);
	    if(l1<l2) ans=add(ans,ans); else if(l1>l2) return puts("0"),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;ans=mul(ans,f[cnt[i++]]))
    {
	f[0]=1,f[1]=1+(i^1&&i&1);
	for(int j=2;j<=cnt[i];++j) f[j]=add(mul(i,mul(j-1,f[j-2])),mul(f[1],f[j-1]));
    }
    printf("%d",ans);
}