#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

#define all(a) begin(a), end(a)
#define len(a) int((a).size())

#ifdef LOCAL
    #include "debug.h"
#else
    #define dbg(...)
    #define dprint(...)
    #define debug if constexpr (false)
    #define draw_tree(...)
    #define draw_array(...)
#endif // LOCAL

// MOD assumed to be prime

template<typename T>
int normalize(T value, int mod) {
    if (value < -mod || value >= 2 * mod)
        value %= mod;

    if (value < 0)
        value += mod;

    if (value >= mod)
        value -= mod;

    return value;
}

template<typename T>
struct dynamic_modular_int {
    using mint = dynamic_modular_int<T>;

    int value;

    dynamic_modular_int() : value(0) {}
    dynamic_modular_int(const mint &x) : value(x.value) {}

    template<typename U, typename V = std::enable_if_t<std::is_integral<U>::value>>
    dynamic_modular_int(U value) : value(normalize(value, T::mod)) {}

    template<typename U>
    mint power(U degree) const {
        mint prod = 1;
        mint a = *this;

        for (; degree > 0; degree >>= 1, a *= a)
            if (degree & 1)
                prod *= a;

        return prod;
    }

    mint inv() const {
        return power(T::mod - 2);
    }

    mint& operator=(const mint &x) {
        value = x.value;
        return *this;
    }

    mint& operator+=(const mint &x) {
        value += x.value;
        if (value >= T::mod)
            value -= T::mod;

        return *this;
    }

    mint& operator-=(const mint &x) {
        value -= x.value;
        if (value < 0)
            value += T::mod;

        return *this;
    }

    mint& operator*=(const mint &x) {
        value = (long long) value * x.value % T::mod;
        return *this;
    }

    mint& operator/=(const mint &x) {
        return *this *= x.inv();
    }

    friend mint operator+(const mint &x, const mint &y) {
        return mint(x) += y;
    }

    friend mint operator-(const mint &x, const mint &y) {
        return mint(x) -= y;
    }

    friend mint operator*(const mint &x, const mint &y) {
        return mint(x) *= y;
    }

    friend mint operator/(const mint &x, const mint &y) {
        return mint(x) /= y;
    }

    mint& operator++() {
        ++value;
        if (value == T::mod)
            value = 0;

        return *this;
    }

    mint& operator--() {
        --value;
        if (value == -1)
            value = T::mod - 1;

        return *this;
    }

    mint operator++(int) {
        mint prev = *this;
        value++;
        if (value == T::mod)
            value = 0;

        return prev;
    }

    mint operator--(int) {
        mint prev = *this;
        value--;
        if (value == -1)
            value = T::mod - 1;

        return prev;
    }

    mint operator-() const {
        return mint(0) - *this;
    }

    bool operator==(const mint &x) const {
        return value == x.value;
    }

    bool operator!=(const mint &x) const {
        return value != x.value;
    }

    template<typename U>
    explicit operator U() {
        return value;
    }

    friend std::istream& operator>>(std::istream &in, mint &x) {
        std::string s;
        in >> s;
        x = 0;
        bool neg = s[0] == '-';
        for (const auto c : s)
            if (c != '-')
                x = x * 10 + (c - '0');

        if (neg)
            x *= -1;

        return in;
    }

    friend std::ostream& operator<<(std::ostream &out, const mint &x) {
        return out << x.value;
    }
};

struct dynamic_modular_int_mod {
    static int mod;
};

int dynamic_modular_int_mod::mod = 998244353;
int &MOD = dynamic_modular_int_mod::mod;

using mint = dynamic_modular_int<dynamic_modular_int_mod>;

constexpr int N = 1010;
mint choose[N][N];

void precalc() {
    for (int i = 0; i < N; i++) {
        choose[i][0] = choose[i][i] = 1;
        for (int j = 1; j < i; j++) {
            choose[i][j] = choose[i - 1][j - 1] + choose[i - 1][j];
        }
    }
}

void solve(int /* test_num */) {
    int n, m;
    cin >> n >> m;

    const int K = min(n + 3, m) + 1;
    vector dp(n + 1, vector<mint>(K));
    fill(all(dp[0]), 1);

    mint total = mint(m).power(n);
    mint ans = 0;
    for (int mx = 1; mx <= n; mx++) {
        const int K = min(n / mx + 2, m) + 1;
        for (int cnt = 1; cnt <= n; cnt++) {
            for (int d = 0; d < K; d++) {
                dp[cnt][d] = (m - d) * dp[cnt - 1][d];
                if (cnt >= mx && d + 1 < K) {
                    dp[cnt][d] -= (m - d) * choose[cnt - 1][mx - 1] * dp[cnt - mx][d + 1];
                }
            }
        }
        ans += total - dp[n][0];
    }
    cout << ans << '\n';
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int tests;
    cin >> tests >> MOD;
    precalc();
    for (int test_num = 1; test_num <= tests; test_num++) {
        solve(test_num);
    }
}