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 <fstream>
#include <vector>

using namespace std;

//ifstream cin("tema.in");
//ofstream cout("tema.out");

const int MAXN = 100000;
const int MOD = 1000000007;

int after[1 + MAXN], inDegree[1 + MAXN], tail[1 + MAXN], cycles[1 + MAXN], dp[1 + MAXN];
int cycle[1 + MAXN];
bool seen[1 + MAXN];

int Tail(int before, int now, int down, int length) {
    int delta = (before < now ? now - before : length - before + now);
    if (delta < down)
        return 0;
    if (delta == down)
        return 1;
    return 2;
}

int Ways(int l, int n) {
    dp[0] = 1;
    int single = 1;
    if (l % 2 && l > 1)
        single++;
    dp[1] = single;
    for (int i = 2; i <= n; i++)
        dp[i] = (1LL * ((1LL * l * (i - 1)) % MOD) * dp[i - 2] + 1LL * single * dp[i - 1]) % MOD;
    return dp[n];
}

int main() {
    //freopen("tema.in", "r", stdin);
    //freopen("tema.out", "w", stdout);
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &after[i]);
        inDegree[after[i]]++;
    }
    for (int i = 1; i <= n; i++)
        if (inDegree[i] > 2) {
            printf("0\n");
            return 0;
        }
    for (int i = 1; i <= n; i++)
        if (!inDegree[i]) {
            int j = i, length = 0;
            while (inDegree[j] < 2) {
                seen[j] = true;
                length++;
                j = after[j];
            }
            tail[j] = length;
        }
    int answer = 1;
    for (int i = 1; i <= n; i++)
        if (!seen[i]) {
            int j = i, length = 0;
            bool hasTail = false;
            while (!seen[j]) {
                length++;
                cycle[length] = j;
                if (tail[j])
                    hasTail = true;
                seen[j] = true;
                j = after[j];
            }
            if (i != j) {
                printf("0\n");
                return 0;
            }
            if (!hasTail) {
                cycles[length]++;
                continue;
            }
            j = 1;
            while (!tail[cycle[j]])
                j++;
            int before = j;
            for (int k = (j == length ? 1 : j + 1); k != j; k == length ? k = 1 : k++)
                if (tail[cycle[k]]) {
                    answer = (1LL * answer * Tail(before, k, tail[cycle[k]], length)) % MOD;
                    before = k;
                }
            answer = (1LL * answer * Tail(before, j, tail[cycle[j]], length)) % MOD;
        }
    for (int i = 1; i <= n; i++)
        answer = (1LL * answer * Ways(i, cycles[i])) % MOD;
    printf("%d\n", answer);
    return 0;
}