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>

#define For(i, j, k) for(int i = j; i <= k; i++)

using namespace std;

const int N = 100010;
const int Mod = 1e9 + 7;

int n;
int to[N], deg[N], pre[N];
int cnt[N], f[N];
bool vis[N];

int main(){

	scanf("%d", &n);
	For(i, 1, n) scanf("%d", &to[i]), deg[to[i]]++;
	For(i, 1, n) if(deg[i] > 2){
		puts("0");
		return 0;
	} 

	For(i, 1, n) if(deg[i] == 2 && !vis[i]){
		int o = i;
		do{
			pre[to[o]] = o;
			if(vis[o]){
				puts("0");
				return 0;
			}
			vis[o] = true;
			o = to[o];
		}while(o != i);
	}

	int ans = 1;

	For(i, 1, n) if(!deg[i]){
		int o = i, len = 0;
		while(!vis[o]) vis[o] = true, o = to[o], ++len;
		
		int len2 = 0;
		do{
			o = pre[o];
			++len2;
		}while(deg[o] == 1);

		if(len < len2) ans = ans * 2 % Mod;
		else if(len > len2){
			puts("0");
			return 0;
		}
	}

	For(i, 1, n) if(!vis[i]){
		int o = i, len = 0;
		do{
			vis[o] = true;
			o = to[o];
			++len;
		}while(o != i);
		cnt[len]++;
	}

	For(i, 1, n) if(cnt[i]){
		int x = i > 1 && i % 2 == 1 ? 2 : 1;
		f[0] = 1, f[1] = x;
		For(j, 2, cnt[i]) f[j] = (1ll * (j - 1) * i * f[j - 2] + f[j - 1] * x) % Mod;
		ans = 1ll * ans * f[cnt[i]] % Mod;
	}
	printf("%d\n", ans);

	return 0;
}