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>
#define MAXN 100000
#define MO 1000000007
using namespace std;
int a[MAXN+5],pre[MAXN+5],n;
int d[MAXN+5],cnt[MAXN+5],f[MAXN+5];
bool vis[MAXN+5];
int main()
{
//	freopen("test.in","r",stdin);
//	freopen("test.out","w",stdout);
	int ans=1;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]),d[a[i]]++;
	for(int i=1;i<=n;i++)
	{
		if(d[i]>=3)
		{
			printf("0\n");
			return 0;
		}
		if(d[i]<=1||vis[i]==true)
			continue;
		int p=i;
		do
		{
			if(vis[p]==true)
			{
				printf("0\n");
				return 0;
			}
			vis[p]=true;
			pre[a[p]]=p;
			p=a[p];
		}while(p!=i);
	}
	for(int i=1;i<=n;i++)
	{
		if(d[i]==0)
		{
			int p=i,len1=0,len2=0;
			while(vis[p]==false)
				vis[p]=true,len1++,p=a[p];
			do
			{
				p=pre[p];
				len2++;
			}while(d[p]!=2);
			if(len1<len2)
				ans=2LL*ans%MO;
			else if(len1>len2)
			{
				printf("0\n");
				return 0;
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(vis[i]==false)
		{
			int p=i,len=0;
			do
			{
				p=a[p];
				len++;
				vis[p]=true;
			}while(p!=i);
			cnt[len]++;
		}
	}
	for(int i=1;i<=n;i++)
	{
		int mul=1;
		if(i!=1&&(i%2==1))
			mul++;
		f[0]=1,f[1]=mul;
		for(int j=2;j<=cnt[i];j++)
			f[j]=(1LL*f[j-2]*(1LL*j-1LL)%MO*i%MO+1LL*f[j-1]*mul%MO)%MO;
		ans=(1LL*ans*f[cnt[i]])%MO;
	}
	printf("%d\n",ans);
	return 0;
}