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;

const int mod = 1e9+7;

int in[100010];
int a[100010];
int vis[100010],line[100010],cycc[100010];
vector<vector<int> > cyc;
bool oncyc[100010];
long long int dp[100010];
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i],in[a[i]]++;
	for(int i=1;i<=n;i++)
		if(!in[i]){
			int u=i;vis[i]=i;while(!vis[a[u]])	u=a[u],vis[u]=i;
			if(vis[a[u]]==i){
				cyc.push_back({});
				cyc.back().push_back(u);
				for(int j=u;a[j]!=u;j=a[j])
					cyc.back().push_back(a[j]);
				for(auto it:cyc.back())
					oncyc[it]=true;
			}
			else if(!oncyc[a[u]]||line[a[u]]){
				cout<<0<<endl;
				return 0;
			}
			int cnt=0;
			for(int j=i;j!=a[u];j=a[j])	cnt++;
			line[a[u]]=cnt;
		}
	for(int i=1;i<=n;i++)
		if(!vis[i]){
			int cnt=0;
			for(int j=i;!vis[j];j=a[j])	cnt++,vis[j]=i;
			cycc[cnt]++;
		}
	long long int ans=1;
	for(int i=1;i<=n;i++){
		int cnt=cycc[i];
		dp[0]=1;
		dp[1]=1;
		if(i>1&&(i&1))
			dp[1]++;
		for(int j=2;j<=cnt;j++)
			dp[j]=(dp[j-1]*dp[1]+dp[j-2]*(j-1)*i)%mod;
		ans=ans*dp[cnt]%mod;
	}
	for(auto it:cyc){
		reverse(it.begin(),it.end());
		int sz=it.size();
		int last=sz;
		for(int i=0;i<sz;i++,last++)
			if(line[it[i]])	break;
		for(int i=sz-1;i>=0;i--)
			if(line[it[i]]){
				int l1=line[it[i]],l2=last-i;
				if(l1>l2)
					ans=0;
				else if(l1<l2)
					ans=ans*2%mod;
				last=i;
			}
	}
	cout<<ans<<endl;
}