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<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(a) int(a.size())
const int N=1e5+10;
const int mod=1e9+7;

int gi() {
	int x=0,o=1;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if(ch=='-') o=-1,ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x*o;
}

int n,a[N],in[N],ans=1,cnt[N],fa[N],f[N],pre[N];
bool vis[N];
vi vec[N];

int getf(int x) {
	return x==fa[x]?x:fa[x]=getf(fa[x]);
}

void No() {
	cout<<0;exit(0);
}

int main() {
	cin>>n;
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=n;i++) a[i]=gi(),++in[a[i]],fa[getf(i)]=getf(a[i]);
	for(int i=1;i<=n;i++) if(in[i]>2) No();
	for(int i=1;i<=n;i++) vec[getf(i)].pb(i);
	for(int u=1;u<=n;u++)
		if(getf(u)==u) {
			bool fl=1;int sz=0;
			for(auto x:vec[u]) {
				++sz;
				if(in[x]!=1) fl=0;
			}
			//cerr<<u<<' '<<fl<<' '<<sz<<'\n';
			if(fl) ++cnt[sz];
			else {
				int now=u;
				while(!vis[now]) vis[now]=1,now=a[now];
				for(auto x:vec[u]) vis[x]=0;
				while(!vis[now]) vis[now]=1,pre[a[now]]=now,now=a[now];
				for(auto x:vec[u])
					if(in[x]>1&&!vis[x]) No();
				for(auto x:vec[u])
					if(!in[x]) {
						int now=x,l1=0,l2=0;
						while(!vis[now]) ++l1,now=a[now];
						++l2;now=pre[now];
						while(in[now]==1) ++l2,now=pre[now];
						//cerr<<l1<<' '<<l2<<'\n';
						if(l1>l2) No();
						if(l1<l2) ans=2ll*ans%mod;
					}
			}
		}
	for(int k=1;k<=n;k++) {
		for(int i=0;i<=cnt[k];i++) f[i]=0;
		f[0]=1;
		for(int i=1;i<=cnt[k];i++) {
			f[i]=f[i-1]*((k&1)&&k>1?2:1)%mod;
			if(i>1) f[i]=(f[i]+1ll*f[i-2]*(i-1)%mod*k)%mod;
		}
		ans=1ll*ans*f[cnt[k]]%mod;
		//cerr<<"k,cnt[k]="<<k<<' '<<cnt[k]<<'\n';
	}
	cout<<ans;
	return 0;
}