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<bits/stdc++.h>
using namespace std;
#define LL long long

const int maxn=1e5+10;
const int mo=1e9+7;

int n,f[maxn],Ans=1,deg[maxn];
int feet[maxn],sz[maxn],dp[maxn];
bool vis[maxn],cir[maxn];
queue<int> q;

int main()
{
#ifdef h10
	freopen("E.in","r",stdin);
	freopen("E.out","w",stdout);
#endif
	int i,j,u;
	scanf("%d",&n);
	for (i=1;i<=n;i++)
	{
		scanf("%d",&f[i]);
		deg[f[i]]++;
	}
	for (i=1;i<=n;i++)
		if (deg[i]>2) {puts("0"); return 0;}
	for (i=1;i<=n;i++)
		if (!deg[i]) q.push(i);

	while (!q.empty())
	{
		u=q.front(); q.pop();
		if (!(--deg[f[u]])) q.push(f[u]);
	}
	for (i=1;i<=n;i++) cir[i]=deg[i]!=0;
	memset(deg,0,sizeof(deg));
	for (i=1;i<=n;i++) deg[f[i]]++;

	for (i=1;i<=n;i++)
		if (!cir[i]&&deg[i]==2) {puts("0"); return 0;}

//	for (i=1;i<=n;i++)
//		printf("%d ",cir[i]);
//	puts("");

	for (i=1;i<=n;i++)
		if (deg[i]==0)
		{
			int cnt=0;
			for (u=i;!cir[u];u=f[u]) cnt++;
			feet[u]=cnt;
//			printf("feet[%d]=%d\n",u,cnt);
		}

	for (i=1;i<=n;i++)
		if (cir[i]&&!vis[i])
		{
			int cnt=0,flag=1,pos=0;
			for (u=i;;u=f[u])
			{
				vis[u]=1;
				cnt++;
				if (feet[u]) flag=0,pos=u;
				if (f[u]==i) break;
			}
			if (flag) sz[cnt]++;
			else
			{
				cnt=0;
				for (u=f[pos];;u=f[u])
				{
					cnt++;
					if (feet[u])
					{
						if (feet[u]<cnt) Ans=Ans*2%mo;
						if (feet[u]>cnt) Ans=0;
						cnt=0;
					}
					if (u==pos) break;
				}
			}
		}

	for (i=1;i<=n;i++)
		if (sz[i])
		{
//			printf("sz[%d]=%d\n",i,sz[i]);
			dp[0]=1;
			for (j=1;j<=sz[i];j++)
			{
				if (i>1&&i&1) dp[j]=dp[j-1]*2%mo;
				else dp[j]=dp[j-1];
				if (j>1) (dp[j]+=(LL)dp[j-2]*(j-1)%mo*i%mo)%=mo;
			}
//			printf("dp[%d]=%d\n",sz[i],dp[sz[i]]);
			Ans=(LL)Ans*dp[sz[i]]%mo;
		}
	printf("%d\n",Ans);
}