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<cmath>
#include<algorithm>
#include<vector>
using namespace std;
const int N=200005,md=1000000007;
vector<int> vct[N];
int n,i,j,k,a[N],p[N],d[N],fa[N],ans=1,cnt,size[N],huan[N],f[N],c[N],num[N],head[N],adj[N],nxt[N],pre[N],u[N];
bool oh[N],v[N];
int find(int x)
{
	return !fa[x]?x:fa[x]=find(fa[x]);
}
void dfs(int x)
{
	v[x]=true;
	p[++cnt]=x;
	if(!v[a[x]])
		dfs(a[x]);
	else
	{
		int i;
		for(i=cnt;i>=1;--i)
			if(p[i]==a[x])
				break;
		if(i>=1)
		{
			int fst=0,lst=0,st=i;
			while(i<=cnt)
			{
				if(d[p[i]]>1)
				{
					if(!fst)
						fst=i;
					pre[p[i]]=i-lst;
					lst=i;
				}
				oh[p[i]]=true;
				huan[find(x)]++;
				++i;
			}
			pre[p[fst]]=fst-st+1+cnt-lst;
		}
	}
}
int work(int x)
{
	int rtn=1;
	for(int y=head[x];y;y=nxt[y])
		if(!oh[adj[y]])
			rtn+=work(adj[y]);
	return rtn;
}
int main()
{
	scanf("%d",&n);
	for(i=1;i<=n;++i)
	{
		scanf("%d",a+i);
		adj[i]=i;
		nxt[i]=head[a[i]];
		head[a[i]]=i;
		++d[a[i]];
		if(find(i)!=find(a[i]))
			fa[find(i)]=find(a[i]);
	}
	for(i=1;i<=n;++i)
		vct[find(i)].push_back(i);
	for(i=1;i<=n;++i)
		if(d[i]>2)
		{
			printf("0");
			return 0;
		}
	for(i=1;i<=n;++i)
	{
		size[find(i)]++;
		if(!v[i])
		{
			cnt=0;
			dfs(i);
		}
	}
	for(i=1;i<=n;++i)
		if(!oh[i]&&d[i]>1)
		{
			printf("0");
			return 0;
		}
	for(i=1;i<=n;++i)
		if(d[i]>1)
			c[find(i)]++;
	for(i=1;i<=n;++i)
		if(d[i]>1)
			u[i]=work(i)-1;
	for(i=1;i<=n;++i)
		if(d[i]>1)
		{
			if(u[i]<pre[i])
				ans=ans*2%md;
			else if(u[i]>pre[i])
			{
				printf("0");
				return 0;
			}
		}
	for(i=1;i<=n;++i)
		if(find(i)==i)
		{
			if(c[i]==0)
				++num[size[i]];
		}
	for(i=1;i<=n;++i)
		if(num[i])
		{
			f[0]=1,f[1]=(i==1?1:i&1?2:1);
			for(j=2;j<=num[i];++j)
				f[j]=(1ll*f[j-1]*(i==1?1:i&1?2:1)%md+1ll*(j-1)*f[j-2]%md*i%md)%md;
			ans=1ll*ans*f[num[i]]%md;
		}
	printf("%d",ans);
	return 0;
}