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>
#define ll long long
#define P 1000000007
int a[100005],in[100005],col[100005],cnt[100005],n,foot[100005];bool cir[100005];long long dp[100005],ans=1;
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;++i) scanf("%d",&a[i]),++in[a[i]];
    for (int i=1;i<=n;++i)
	{
        if (col[i]) continue;int x=i;
        for(;!col[x];x=a[x]) col[x]=i;
        if (col[x]!=i) continue;
        for (;!cir[x];x=a[x]) cir[x]=1; 
    }
    for (int i=1;i<=n;++i) if ((cir[i]&&in[i]>2)||(!cir[i]&&in[i]>1)) {printf("0");return 0;}
    for (int i=1;i<=n;++i)
	{
        if (in[i]) continue;int x=i,tmp=0;
        while(!cir[x]) x=a[x],tmp++;foot[x]=tmp;
    } 
    for (int i=1;i<=n;++i)
	{
        if (!cir[i]) continue;int x=i,st=0,first=0,id=0,len=0;
        while (cir[x])
		{
            ++id;cir[x]=0;
            if (foot[x])
			{
                if (!first){st=first=id;len=foot[x];x=a[x];continue;}
				else
				{
                    int numm=(foot[x]<(id-st))+(foot[x]<=(id-st));
					(ans*=numm)%=P;if (!ans) {printf("0");return 0;}st=id;x=a[x];continue;
                }
            }
			x=a[x];
        }
		if (first)
		{
            int numm=(len<(id+first-st))+(len<=(id+first-st));
            (ans*=numm)%=P;if (!ans) {printf("0");return 0;}
        }
		else cnt[id]++;
    }
    for (int i=1;i<=n;++i)
	{
        dp[0]=1;if (!cnt[i]) continue;
        if (i>1&&(i%2)) for (int j=1;j<=cnt[i];++j) {dp[j]=dp[j-1]*2%P;if (j>1) (dp[j]+=dp[j-2]*(j-1)*i%P)%=P;}
		else for (int j=1;j<=cnt[i];++j){dp[j]=dp[j-1];if (j>1) (dp[j]+=dp[j-2]*(j-1)*i%P)%=P;}   
        (ans*=dp[cnt[i]])%=P;if (!ans){printf("0");return 0;}
    }
	printf("%lld",ans);
}