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<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
#define ll long long
#define inf 0x3f3f3f3f
#define mod 1000000007
#define maxn 200010
inline ll read()
{
	ll x=0; char c=getchar(),f=1;
	for(;c<'0'||'9'<c;c=getchar())if(c=='-')f=-1;
	for(;'0'<=c&&c<='9';c=getchar())x=x*10+c-'0';
	return x*f;
}
inline void write(ll x)
{
	static char buf[20];
	int len=0;
	if(x<0)putchar('-'),x=-x;
	for(;x;x/=10)buf[len++]=x%10+'0';
	if(!len)putchar('0');
	else while(len)putchar(buf[--len]);
}
inline void writesp(ll x){write(x); putchar(' ');}
inline void writeln(ll x){write(x); putchar('\n');}
int p[maxn],vis[maxn],col[maxn],mark[maxn],dep[maxn],rt[maxn],deg[maxn];
int len[maxn],dis[maxn];
int cnt[maxn],f[maxn];
std::vector<int>a;
int n,tot;
int main()
{
	// freopen("agc008E.in","r",stdin);
	// freopen("agc008E.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++)
		p[i]=read();
	for(int i=1;i<=n;i++)
		if(!vis[i]){
			int now=i;
			while(!vis[now]){
				a.push_back(now); vis[now]=1;
				now=p[now];
			}
			if(col[now]){
				int sz=a.size();
				for(int j=sz-1;j>=0;j--)
					col[a[j]]=col[now],rt[a[j]]=rt[now],dep[a[j]]=dep[now]+(sz-j);
			}
			else{
				int sz=a.size(),flag=0;
				++tot;
				for(int j=sz-1;j>=0;j--){
					col[a[j]]=tot;
					if(!flag)mark[a[j]]=1,rt[a[j]]=a[j],dep[a[j]]=0;
					else rt[a[j]]=now,dep[a[j]]=dep[a[j+1]]+1;
					flag|=(a[j]==now);
				}
			}
			a.clear();
		}
	for(int i=1;i<=n;i++)
		if(!mark[i])++deg[p[i]];
	for(int i=1;i<=n;i++)
		if(deg[i]>=2){
			puts("0"); return 0;
		}
	for(int i=1;i<=n;i++)
		len[rt[i]]=std::max(len[rt[i]],dep[i]);
	memset(vis,0,sizeof(vis));
	ll ans=1;
	for(int i=1;i<=n;i++)
		if(mark[i]&&!vis[i]){
			a.push_back(i); vis[i]=1;
			int now=p[i];
			while(now!=i){
				a.push_back(now); vis[now]=1;
				now=p[now];
			}
			int flag=0,sz=a.size();
			for(int j=0;j<sz;j++)
				if(len[a[j]]){
					flag=1; break;
				}
			if(flag){
				int last=-1,first=-1;
				for(int j=0;j<sz;j++)
					if(len[a[j]]){
						if(~first)dis[a[j]]=j-last;
						else first=j;
						last=j;
					}
				dis[a[first]]=first+sz-last;
				for(int j=0;j<sz;j++)
					if(len[a[j]]){
						if(len[a[j]]<dis[a[j]])ans=ans*2%mod;
						else if(len[a[j]]>dis[a[j]]){
							puts("0"); return 0;
						}
					}
			}
			else ++cnt[sz];
			a.clear();
		}
	for(int i=1;i<=n;i++){
		int w=((i&1)&&(i>1))?2:1;
		f[0]=1; f[1]=w;
		for(int j=2;j<=cnt[i];j++)
			f[j]=(f[j-1]*w+(ll)(j-1)*f[j-2]%mod*i)%mod;
		ans=ans*f[cnt[i]]%mod;
	}
	writeln(ans);
	return 0;
}