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<cstring>
#include<algorithm>
using namespace std;
const int MAXN=100005,MOD=1000000007;

int n,A[MAXN],deg[MAXN],pre[MAXN];
int cnt[MAXN],dp[MAXN];
int ans=1;
bool vis[MAXN];

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)
		{puts("0");return 0;}
		if(deg[i]<2||vis[i])
			continue;
		int u=i;
		do
		{
			if(vis[u])
			{puts("0");return 0;}
			vis[u]=true;
			pre[A[u]]=u;
			u=A[u];
		}while(u!=i);
	}
	for(int i=1;i<=n;i++)
		if(deg[i]==0)
		{
			int u=i;
			int len1=0,len2=0;
			while(!vis[u])
			{
				len1++;
				vis[u]=true;
				u=A[u];
			}
			do
			{
				len2++;
				u=pre[u];
			}while(deg[u]!=2);
			if(len2<len1)
			{puts("0");return 0;}
			else if(len2>len1)
				ans=ans*2%MOD;
		}
	for(int i=1;i<=n;i++)
		if(!vis[i])
		{
			int len=0;
			int u=i;
			do
			{
				len++;
				vis[u]=true;
				u=A[u];
			}while(u!=i);
			cnt[len]++;
		}
	for(int i=1;i<=n;i++)
	{
		int mul=1;
		if(i!=1&&i%2==1)
			mul=2;
		dp[0]=1;
		dp[1]=mul;
		for(int j=2;j<=cnt[i];j++)
			dp[j]=(1LL*dp[j-2]*(j-1)%MOD*i%MOD+1LL*dp[j-1]*mul%MOD)%MOD;
		ans=1LL*ans*dp[cnt[i]]%MOD;
	}
	
	printf("%d\n",ans);
	
	return 0;
}