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<vector>
using namespace std;

#define sz(x) (int)x.size()
const int _ = 1e5 + 7 , P = 1e9 + 7;
vector < int > nxt1[_] , nxt2[_]; int N;

bool vis[_] , incirc[_];

int dfs1(int x , vector < int > &pot){
	vis[x] = 1; int r = 0;
	for(auto t : nxt1[x])
		if(!vis[t]){int v = dfs1(t , pot); if(v){pot.push_back(x); incirc[x] = 1; r = v;}}
		else if(vis[t] && !incirc[t]){r = t; pot.push_back(x); incirc[x] = 1;}
	return r == x ? 0 : r;
}

int dfs2(int x){
	int len = 0; vis[x] = 1;
	for(auto t : nxt2[x])
		if(!incirc[t]) if(!len) len = dfs2(t) + 1; else len = -1e9;
	return len;
}

int main(){
	scanf("%d" , &N); for(int i = 1 ; i <= N ; ++i){int x; scanf("%d" , &x); nxt1[i].push_back(x); nxt2[x].push_back(i);}
	int ans = 1; static int num[_];
	for(int i = 1 ; i <= N ; ++i)
		if(!vis[i]){
			vector < int > pot; dfs1(i , pot); vector < pair < int , int > > link;
			for(int i = 0 ; i < sz(pot) ; ++i){
				int p = dfs2(pot[i]); if(p < 0) ans = 0; else if(p > 0) link.push_back(make_pair(i , p));
			}
			if(link.empty()){++num[sz(pot)]; continue;}
			
			for(int i = 1 ; i < sz(link) ; ++i)
				if(link[i].first < link[i - 1].first + link[i - 1].second) ans = 0;
				else if(link[i].first > link[i - 1].first + link[i - 1].second) ans = 2 * ans % P;

			if(link.back().first + link.back().second > link.front().first + sz(pot)) ans = 0;
			else if(link.back().first + link.back().second < link.front().first + sz(pot)) ans = 2 * ans % P;
		}
	
	for(int i = 1 ; i <= N ; ++i)
		if(num[i]){
			static int dp[_]; dp[0] = 1;
			for(int j = 1 ; j <= num[i] ; ++j)
				dp[j] = ((i > 1 && (i & 1) ? 2 : 1) * dp[j - 1] + (j > 1 ? 1ll * dp[j - 2] * (j - 1) % P * i : 0)) % P;
			ans = 1ll * ans * dp[num[i]] % P;
		}
	printf("%d\n" , ans);
	return 0;
}