OIG II - zol

// https://szkopul.edu.pl/problemset/problem/_GcQdStgudaHcnq9XI3qAVWl/site/?key=statement
// OIG II (3 etap)

#include <iostream>
#include <map>
#include <string>

std::map<int, int> m;

constexpr int mod = 10000;

int memo[1000 * 1000];

int silnia(int n) {
    if (n == 0) {
        return 1;
    }

    if (memo[n] != 0) {
        return memo[n];
    }

    auto res = (n * silnia(n - 1)) % mod;
    memo[n] = res;

    return res;
}

int main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);

    int n;
    std::cin >> n;

    for (int i = 0; i < n; i++) {
        int a;
        std::cin >> a;

        m[a]++;
    }

    long long ans = 2;
    long long temp = 2;

    bool flag = false;

    for (const auto& p : m) {
        ans = (ans * silnia(p.second)) % mod;
        temp = temp * silnia(p.second);
        if (temp >= mod) {
            flag = true;
        }
    }

    if (m.size() < 2) {
        ans /= 2;
        temp /= 2;
    }

    std::string real_ans;

    real_ans = std::to_string(ans);

    if (flag) {
        real_ans = std::string(4 - real_ans.size(), '0') + real_ans;
    }

    std::cout << real_ans << '\n';

    return 0;
}