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 <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
typedef long long ll ;
#define rep(i, a, b) for (int i = a; i <= b; ++ i) 
const int N = 100005, M = N << 1, mo = 1e9 + 7 ; 
using namespace std ;

int n, e, ter[M], nxt[M], lnk[N], opt[N], h[N], ans, d[N], q[N], f[N], deg[N] ;
bool vis[N] ;

void add(int x, int y) {
	ter[++ e] = y, nxt[e] = lnk[x], lnk[x] = e ;
}

bool check(int x) {
	vis[x] = false ;
	int he = 0, ta = 1 ;
	opt[1] = x ;
	for ( ; he != ta ; ) {
		++ he ;
		int u = opt[he] ;
		for (int i = lnk[u] ; i; i = nxt[i]) {
			int v = ter[i] ;
			if (vis[v]) {
				vis[v] = false ;
				opt[++ ta] = v ;
			}
		}
	}
	rep(i, 1, ta) {
		int u = opt[i] ;
		for (int j = lnk[u]; j; j = nxt[j]) if (j & 1) {
			int v = ter[j] ;
			++ deg[v] ;
		}
	}
	bool flg = true ;
	rep(i, 1, ta) {
		int u = opt[i] ;
		flg &= deg[u] > 0 ;
	}
	if (flg) {
		++ h[ta] ;
		return true ;
	}
	int heq = 0, taq = 0 ;
	rep(i, 1, ta) {
		int u = opt[i] ;
		d[u] = deg[u] ;
		if (!d[u]) q[++ taq] = u ;
		if (d[u] > 2) return false ;
	}
	for ( ; heq != taq ; ) {
		++ heq ;
		int u = q[heq] ;
		for (int i = lnk[u]; i; i = nxt[i]) if (i & 1) {
			int v = ter[i] ;
			-- d[v] ;
			if (!d[v]) q[++ taq] = v ;
		}
	}
	rep(i, 1, ta) {
		int u = opt[i] ;
		if (!d[u] && deg[u] > 1) return false ;
	}
	heq = taq = 0 ;
	rep(i, 1, ta) {
		int u = opt[i] ;
		if (!deg[u]) q[++ taq] = u, f[u] = 0 ;
	}
	for ( ; heq != taq ; ) {
		++ heq ;
		int u = q[heq] ;
		for (int i = lnk[u]; i; i = nxt[i]) if (i & 1) {
			int v = ter[i] ;
			-- deg[v] ;
			f[v] = f[u] + 1 ;
			if (!deg[v]) q[++ taq] = v ;
		}
	}
	rep(i, 1, ta) {
		int u = opt[i] ;
		if (deg[u]) {
			x = u ;
			break ; 
		}
	}
	d[0] = 0 ;
	d[++ d[0]] = x ;
	for ( ; ; ) {
		int u = d[d[0]] ;
		for (int i = lnk[u]; i; i = nxt[i]) if (i & 1) {
			int v = ter[i] ;
			d[++ d[0]] = v ;
			break ;
		}
		if (d[d[0]] == d[1]) {
			-- d[0] ;
			break ;
		}
	}
	int las = 0 ;
	rep(i, 1, d[0]) if (f[d[i]]) las = i ;
	rep(i, 1, d[0]) if (f[d[i]]) {
		int l1 = f[d[i]], l2 = las >= i ? d[0] - las + i : i - las ;
		if (l1 < l2) ans = ans * 2 % mo ; else
		  if (l1 > l2) ans = 0 ;
		las = i ;
	}
	return true ;
}

inline void upd(int &x, int y) {
	x = (x + y) % mo ; 
}

int main() {
	scanf("%d", &n) ;
	int x ;
	rep(i, 1, n) {
		scanf("%d", &x) ;
		add(i, x), add(x, i) ;
	}
	rep(i, 1, n) vis[i] = true ;
	ans = 1 ;
	rep(i, 1, n) if (vis[i]) {
		if (!check(i)) {
			printf("0\n") ;
			return 0 ;
		}
	}
	rep(L, 1, n) if (h[L]) {
		f[0] = 1 ;
		rep(i, 1, h[L]) {
			f[i] = 0 ;
			upd(f[i], f[i - 1]) ;
			if ((L > 1) && (L & 1)) upd(f[i], f[i - 1]) ;
			if (i > 1) upd(f[i], (ll) (i - 1) * f[i - 2] % mo * L % mo) ;
		}
		ans = (ll) ans * f[h[L]] % mo ;
	}
	printf("%d\n", ans) ;
	return 0 ; 
}