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>
#define mo 1000000007
using namespace std;
int inn[1000100],a[1000100],num[1000100],wei[1000100],mp[1000100],f[1000100];
bool vis[1000100];
int work(int l,int n)
{
	f[0]=1;f[1]=1+(l&1)-(l==1);
	for (int i=2;i<=n;i++)
		f[i]=((1+(l&1)-(l==1))*f[i-1]+(long long)l*(i-1)%mo*f[i-2])%mo;
	return f[n];
}	
int main()
{
	//freopen("in.txt","r",stdin);
	int n;scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);inn[a[i]]++;
		if (inn[a[i]]>2) {printf("0\n");return 0;}
	}
	for (int i=1;i<=n;i++) if (!inn[i])
	{
		int js=0,now=i;
		while (inn[now]!=2) {vis[now]=true;now=a[now];js++;}
		num[now]=js;//cerr<<now<<' '<<js<<endl;
	}
	int ans=1;
	for (int i=1;i<=n;i++) if (!vis[i])
	{
		int len=0,now=i;
		while (!vis[now]) {wei[++len]=now;vis[now]=true;now=a[now];}//cerr<<len<<endl;
		if (i!=now) {printf("0\n");return 0;}
		int lst=1;for (int j=1;j<=len;j++) if (num[wei[j]]) lst=j-len;cerr<<lst<<endl;
		if (lst==1) {mp[len]++;continue;}
		for (int j=1;j<=len;j++) if (num[wei[j]])
		{
			if (j-lst>num[wei[j]]) ans=ans*2%mo;
			if (j-lst<num[wei[j]]) {printf("0\n");return 0;}
			lst=j;
		}
	}
	for (int i=1;i<=n;i++) if (mp[i]) ans=(long long)ans*work(i,mp[i])%mo;
	printf("%d\n",ans);
}