ABC 425

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N;
    cin >> N;

    ll ans = 0;
    rep2(i, 1, N + 1) {
        ans += intpow(-1, i) * intpow(i, 3);
    }
    cout << ans << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N;
    cin >> N;
    vll A(N);
    rep(i, N) cin >> A[i];

    vint P(N);
    iota(all(P), 1);

    do {
        int ok = 1;
        rep(i, N) {
            if (A[i] == -1) continue;
            if (A[i] != P[i]) ok = 0;
        }
        if (ok) {
            Yes();
            print(P);
            return;
        }
    } while (next_permutation(all(P)));

    No();
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, Q;
    cin >> N >> Q;
    fenwick_tree<ll> fw(N);

    rep(i, N) {
        ll a;
        cin >> a;
        fw.add(i, a);
    }

    int start = 0;

    rep(i, Q) {
        int t;
        cin >> t;
        if (t == 1) {
            ll c;
            cin >> c;
            start += c;
            start %= N;
        } else {
            ll l, r;
            cin >> l >> r;
            l--, r--;

            l += start;
            r += start;
            l %= N;
            r %= N;

            if (r < l) {
                cout << fw.sum(l, N) + fw.sum(0, r + 1) << endl;
            } else {
                cout << fw.sum(l, r + 1) << endl;
            }
        }
    }
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll H, W;
    cin >> H >> W;
    vector<string> grid(H);
    rep(i, H) cin >> grid[i];

    vint di = {0, 1, 0, -1};
    vint dj = {1, 0, -1, 0};

    vvint used(H, vint(W));

    using P = pair<int, int>;
    deque<P> deq;
    rep(i, H) rep(j, W) {
        if (grid[i][j] == '#') {
            used[i][j] = 1;
            continue;
        }
        int cnt = 0;
        rep(d, 4) {
            ll ni = i + di[d], nj = j + dj[d];
            if (clamp(ni, 0ll, H - 1) != ni || clamp(nj, 0ll, W - 1) != nj) continue;
            if (grid[ni][nj] == '#') cnt++;
        }
        if (cnt == 1) deq.push_back({i, j});
    }

    while (deq.size()) {
        for (auto [i, j] : deq) {
            grid[i][j] = '#';
            used[i][j] = 1;
        }

        deque<P> deqn;

        for (auto [oi, oj] : deq) {
            rep(d, 4) {
                ll i = oi + di[d], j = oj + dj[d];
                if (clamp(i, 0ll, H - 1) != i || clamp(j, 0ll, W - 1) != j) continue;
                if (grid[i][j] == '#') continue;

                int cnt = 0;
                rep(dd, 4) {
                    ll ni = i + di[dd], nj = j + dj[dd];
                    if (clamp(ni, 0ll, H - 1) != ni || clamp(nj, 0ll, W - 1) != nj) continue;
                    if (grid[ni][nj] == '#') cnt++;
                }
                if (cnt == 1 && used[i][j] == 0) {
                    used[i][j] = 1;
                    deqn.push_back({i, j});
                }
            }
        }

        swap(deq, deqn);
    }

    ll ans = 0;
    rep(i, H) rep(j, W) if (grid[i][j] == '#') ans++;
    cout << ans << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll T, M;
    cin >> T >> M;

    modint::set_mod(M);
    using mint = modint;

    int upper = 5001;
    vector binom(upper, vector<mint>(upper));
    vector checked(upper, vint(upper));
    binom[0][0] = checked[0][0] = 1;

    auto dfs = [&](auto dfs, ll n, ll k) -> mint {
        if (n < 0 || k < 0) return 0;
        if (checked[n][k]) return binom[n][k];
        if (n < k) return 0;
        if (k == 0) return 1;
        mint ret = dfs(dfs, n - 1, k - 1) + dfs(dfs, n - 1, k);
        checked[n][k] = 1;
        return binom[n][k] = ret;
    };

    auto cal = [&]() -> void {
        ll N;
        cin >> N;
        vll C(N);
        rep(i, N) cin >> C[i];

        mint ans = 1;
        ll ctot = accumulate(all(C), 0ll);
        ll sub = 0;
        for (auto c : C) {
            ans *= dfs(dfs, ctot - sub, c);
            sub += c;
        }
        cout << ans.val() << endl;
    };

    while (T--) {
        cal();
    }
}