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>
#define rep(i,j,k) for (i=j;i<=k;i++)
using namespace std;
const int N=1e5+5,mod=1e9+7;
int n,i,j,sz,cir;
int a[N],vis[N],dgr[N],foot[N],cnt[N],dis[N],nc[N];
long long ans,g[N];
void dfs(int x) {
	vis[x]=1; sz++; if (dgr[a[x]]!=1 || nc[a[x]]) cir=0;
	if (vis[a[x]]) return ;
	dfs(a[x]);
}
void dfs2(int x,int step) {
	if (dgr[a[x]]>1) {foot[a[x]]=step; return ;}
	dfs2(a[x],step+1);
}
void dfs3(int x,int step) {
	if (dgr[a[x]]==2) {dis[a[x]]=step; return;}
	dfs3(a[x],step+1);
}
void dp(int n,int k)
{
	int i;
	g[0]=1;
	rep(i,1,n)
	{
		if ((k%2) && (k>1)) g[i]=g[i-1]*2%mod;
		else g[i]=g[i-1];
		if (i>1) g[i]=(g[i]+g[i-2]*(i-1)%mod *k%mod)%mod;
	}
	ans=ans*g[n]%mod;
}
void calc(int x)
{
	if (foot[x]<dis[x]) ans=ans*2%mod;
	else if (foot[x]>dis[x]) ans=0;
}
int main()
{
	//freopen("cycle.in","r",stdin);
	//freopen("cycle.out","w",stdout);
	scanf("%d",&n); ans=1;
	rep(i,1,n) scanf("%d",&a[i]),dgr[a[i]]++;
	rep(i,1,n) if (dgr[i]>2) { printf("0\n"); return 0; }
	rep(i,1,n)
	if (!vis[i])
	{
		sz=0; cir=1;
		dfs(i);
		if (cir) cnt[sz]++;
		else nc[i]=1;
	}
	rep(i,1,n) if (!dgr[i]) dfs2(i,1);
	rep(i,1,n) if (dgr[i]==2) dfs3(i,1);
	rep(i,1,n) if (cnt[i]) dp(cnt[i],i);
	rep(i,1,n) if (dgr[i]==2) calc(i);
	printf("%lld\n",ans);
	return 0;
}