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<iostream>
#include<cstdio>
#include<cstring>

template<typename T>inline void read(T &x)
{
	char c=x=0;
	for(c=getchar();!isdigit(c);c=getchar());
	for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c^48);
}

namespace gg
{
	typedef long long ll;
	const int N=101000,MOD=1000000007;
	ll qpow(ll a,ll b){ll c=1;for(;b;b>>=1,a=a*a%MOD)if(b&1)c=c*a%MOD;return c;}
	struct disjoint_union_set
	{
		int q[N];
		inline void init(int n){for(int i=1;i<=n;i++)q[i]=i;}
		inline int ask(int p){return p==q[p]?p:q[p]=ask(q[p]);}
		inline void link(int u,int v){q[ask(u)]=ask(v);}
		inline bool uni(int u,int v){return ask(u)==ask(v);}
	}d;
	ll fact[N],ifact[N];
	bool is_cir[N],not_leave[N],vis[N];
	int dep[N],cnt[N];
	int s[N];
	int n;
	ll initialize()
	{
		read(n),d.init(n);
		fact[0]=1;
		for(int i=1;i<=n;i++)
		{
			read(s[i]);
			not_leave[s[i]]=1;
			fact[i]=fact[i-1]*i%MOD;
		}
		ifact[n]=qpow(fact[n],MOD-2);
		for(int i=n;i;i--)ifact[i-1]=ifact[i]*i%MOD;

		for(int i=1;i<=n;i++)
		{
			if(d.uni(i,s[i]))
			{
				for(int p=i;!is_cir[p];p=s[p])
					vis[p]=is_cir[p]=1;
			}
			d.link(i,s[i]);
		}

		for(int i=1;i<=n;i++)
			if(!not_leave[i])
			{
				int p=i,w=0;
				for(;!vis[p];p=s[p])
					vis[p]=1,w++;
				if(!is_cir[p] || dep[p])return 0;
				dep[p]=w;
			}

		ll ret=1;
		memset(vis,0,sizeof(vis));
		for(int i=1;i<=n;i++)
			if(dep[i] && !vis[i])
			{
				int p=s[i],w=1;
				for(;!vis[p];vis[p]=1,p=s[p])
				{
					if(dep[p]>w)return 0;
					else if(dep[p])
					{
						if(dep[p]<w)ret=ret*2%MOD;
						w=0;
					}
					w++;
				}
			}

		for(int i=1;i<=n;i++)
			if(!vis[i] && is_cir[i])
			{
				int p=i,w=0;
				for(;!vis[p];vis[p]=1,p=s[p])w++;
				cnt[w]++;
			}


		return ret;
	}
	void solve()
	{
		ll ans,ret,res,tmp;
		if(!(ans=initialize())){printf("0\n");return;}
		for(int x=1;x<=n;x++)
		{
			int K=cnt[x];if(!K)continue;
//			printf("%d : %d\n",x,K);
			res=0;
			for(int i=0;i*2<=K;i++)
			{
				ret=fact[K]*ifact[K-i*2]%MOD*ifact[i]%MOD*qpow(x,i)%MOD;
				tmp=qpow(2,i),tmp=qpow(tmp,MOD-2);
				ret=ret*tmp%MOD;
				if(x>1 && x%2)ret=ret*qpow(2,K-2*i)%MOD;

				res=(res+ret)%MOD;
			}
			ans=ans*res%MOD;
		}
		printf("%lld\n",ans);
	}
}
int main()
{
//	freopen("E.in","r",stdin);
//	freopen("E.out","w",stdout);
	gg::solve();
	return 0;
}