template<constexpr int N>
constexpr array<int, N> gen_up(const ll X, const int MOD) {
    array<int, N> ret;
    ret[0] = 1;
    for (int i = 1;i < N;++i)
        ret[i] = ret[i-1] * X % MOD;
    return ret;
}