int TrueSolution(std::vector<int> vec) {
    std::sort(vec.begin(), vec.end());
    std::vector<int> nn;
    int same = 1;
    for (int i = 1; i < vec.size(); ++i) {
        if (vec[i] == vec[i - 1]) {
            same++;
        } else {
            nn.push_back(same);
            same = 1;
        }
    }
    nn.push_back(same);
    std::vector<int> aa, bb;
    aa.resize(nn[0] + 1, 0);
    aa[aa.size() - 1] = 1;
    // for (int j = 0; j < aa.size(); ++j)
    //     std::cerr << aa[j] << " ";
    // std::cerr << std::endl;
    for (int ii = 1; ii < nn.size(); ++ii) {
        bb.clear();
        bb.resize(nn[ii] + aa.size() + 1, 0);
        for (int l = 0; l < aa.size(); ++l) {
            for (int j = 0; j <= l; ++j) {
                bb[nn[ii] + j] += aa[l];
                bb[nn[ii] + j] %= 123456789;
            }
        }
        aa = bb;
    }
    int ans = 0;
    for (int i = 0; i < aa.size(); ++i) {
        ans += aa[i];
        ans %= 123456789;
    }
    return ans;
}

vector<int> GenerateArr(std::mt19937* gen, int size) {
    vector<int> res;
    std::uniform_int_distribution dist(1, 100);

    res.reserve(size);
    for (int i = 0; i < size; ++i) {
        res.push_back(dist(*gen));
    }
    return res;
}

void Test() {
    vector<int> arr;
    std::mt19937 gen(143);
    for (int i = 1; i <= 400; ++i) {
        for (int j = 0; j < 10; ++j) {
            arr = GenerateArr(&gen, i);
            std::sort(arr.begin(), arr.end());
            auto calcRes = calc(arr);
            auto myRes = GetTreesCount(arr);
            if (calcRes == myRes) {
                std::cerr << "OK " << i << "-" << j + 1 << std::endl;
            } else {
                std::cerr << "FAIL " << i << "-" << j + 1 << ". Expected: " << calcRes << " and get: " << myRes << std::endl;
            }
        }
    }
    std::cout << calc(arr) << "\n";
    std::cout << GetTreesCount(arr) << "\n";
}