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:
//Heaplax
//别让自己后悔
#include<bits/stdc++.h>
#define N 100005
#define LL long long
#define LOG(x) cerr<<#x<<" = "<<x<<endl
#define add_edge(u,v) nxt[++cnt]=head[u],head[u]=cnt,to[cnt]=v
#define open(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
char ch;bool fs;void re(int& x)
{
	while(ch=getchar(),ch<33);
	if(ch=='-')fs=1,x=0;else fs=0,x=ch-48;
	while(ch=getchar(),ch>33)x=x*10+ch-48;
	if(fs)x=-x;
}
using namespace std;
const int mod=1000000007;
vector<int> cir[N];
int n,ans=1,cnt,a[N],d[N],sy[N],fl[N],sum[N],f[N];
int vis[N];
int main()
{
	re(n);
	for(int i=1;i<=n;++i)
		re(a[i]),++d[a[i]];
	for(int i=1;i<=n;++i)
		if(!d[i])
		{
			static int st[N];
			int top=0,now=i;
			while(!vis[now])
			{
				st[++top]=now;
				vis[now]=i;
				now=a[now];
			}
			if(sy[now])
			{
				if(fl[now])return puts("0"),0;
				fl[now]=top;
			}
			else if(vis[now]!=i)return puts("0"),0;
			else
			{
				++cnt;
				while(st[top]!=now)
				{
					cir[cnt].push_back(st[top]);
					sy[st[top]]=cnt;
					--top;
				}
				--top;
				cir[cnt].push_back(now);
				sy[now]=cnt;
				fl[now]=top;
			}
		}
	for(int i=1;i<=n;++i)
		if(!vis[i])
		{
			int now=i,len=0;
			do
			{
				++len;
				vis[now]=1;
				now=a[now];
			}
			while(now!=i);
			++sum[len];
		}
	// LOG(ans);
	for(int i=1;i<=n;++i)
	{
		f[0]=1;
		for(int j=1;j<=sum[i];++j)
		{
			f[j]=f[j-1];
			if((i&1) && i>1)f[j]=(f[j]+f[j-1])%mod;
			if(j>=2)f[j]=(f[j]+(j-1ll)*i%mod*f[j-2])%mod;
		}
		ans=1ll*ans*f[sum[i]]%mod;
		// LOG(ans);
	}
	// LOG(ans);
	// LOG(cnt);
	for(int i=1;i<=cnt;++i)
	{
		// for(int j:cir[i])cerr<<fl[j]<<" ";
		// cerr<<endl;
		reverse(cir[i].begin(),cir[i].end());
		int last=0;
		for(int j=1;j<cir[i].size();++j)if(fl[cir[i][j]])
		{
			if(j-last>fl[cir[i][j]])ans=ans*2%mod;
			else if(j-last<fl[cir[i][j]])return puts("0"),0;
			last=j;
		}
		// LOG(ans);
		if(cir[i].size()-last>fl[cir[i][0]])ans=ans*2%mod;
		else if(cir[i].size()-last<fl[cir[i][0]])return puts("0"),0;
	}
	printf("%d\n",ans);
}
/*
1 2
2 1
3 4
4 3
5 6
6 7
7 5
8 9
9 10
10 8
11 8
12 9
13 11
*/