#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

u32 P;

constexpr int N = 1000;
constexpr int B = 30;

std::vector<std::vector<u32>> f[N + 2];
u32 binom[N + 1][N + 1];

void inc(u32 &a, u32 b) {
    a += b;
    if (a >= P) {
        a -= P;
    }
}

u32 add(u32 a, u32 b) {
    inc(a, b);
    return a;
}

u32 power(u32 a, i64 b) {
    u32 res = 1;
    for (; b; b /= 2, a = 1ULL * a * a % P) {
        if (b % 2) {
            res = 1ULL * res * a % P;
        }
    }
    return res;
}

void solve() {
    int n, m;
    std::cin >> n >> m;
    
    u32 ans = n;
    for (int i = 0; i < n; i++) {
        ans = 1ULL * ans * m % P;
    }
    
    int a = m;
    std::vector<u32> bm(n + 1), g(n + 1);
    bm[0] = 1;
    g[0] = 1;
    g[1] = 1;
    
    for (; a; a /= 2) {
        if (a % 2 == 1) {
            for (int i = n; i >= 0; i--) {
                u32 v = bm[i];
                bm[i] = 0;
                for (int j = 0; j <= n - i; j++) {
                    inc(bm[i + j], 1ULL * v * g[j] % P);
                }
            }
        }
        std::vector<u32> tmp(n + 1);
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n - i; j++) {
                inc(tmp[i + j], 1ULL * g[i] * g[j] % P);
            }
        }
        g = tmp;
    }
    
    for (int M = 1; M <= n; M++) {
        if (M >= B) {
            for (int i = 0; i <= std::min(m, n / M); i++) {
                u32 pw = bm[i];
                for (int j = n; j >= i * M; j--) {
                    inc(ans, 1ULL * (i % 2 ? f[M][i][j] : P - f[M][i][j]) * pw % P * binom[n][j] % P);
                    pw = 1ULL * pw * (m - i) % P;
                }
            }
        } else {
            std::vector<u32> f(n + 1);
            f[0] = 1;
            for (int i = 0; i < n; i++) {
                u32 res = 0;
                for (int j = 0; j < M - 1 && j <= i; j++) {
                    inc(res, 1ULL * m * f[i - j] % P * binom[i][j] % P);
                }
                for (int j = 1; j < M && j <= i; j++) {
                    inc(res, 1ULL * f[i - j + 1] * (P - binom[i][j]) % P);
                }
                f[i + 1] = res;
            }
            inc(ans, P - f[n]);
        }
    }
    
    std::cout << ans << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t;
    std::cin >> t >> P;
    
    for (int i = 0; i <= N; i++) {
        binom[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            binom[i][j] = add(binom[i - 1][j], binom[i - 1][j - 1]);
        }
    }
    
    f[N + 1].resize(1, std::vector<u32>(N + 1));
    f[N + 1][0][0] = 1;
    for (int x = N; x >= B; x--) {
        f[x].resize(N / x + 1, std::vector<u32>(N + 1));
        for (int m = 0; m <= N / x; m++) {
            u32 b = 1;
            for (int i = 0; i <= m; i++) {
                if (i > 0) {
                    b = 1ULL * b * binom[i * x][x] % P;
                }
                if (m - i <= N / (x + 1)) {
                    for (int j = i * x; j <= N; j++) {
                        inc(f[x][m][j], 1ULL * f[x + 1][m - i][j - i * x] * b % P * binom[j][i * x] % P * binom[m][i] % P);
                    }
                }
            }
        }
    }
    
    while (t--) {
        solve();
    }
    
    return 0;
}