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

const int N = 1e3 + 10;
typedef long long ll;
int T, n;
ll m, P, f[N][N], C[N][N], ans;

struct Mod{
    ll m, p;
    void init(int pp){
        m = ((__int128)1 << 64) / pp;
        p = pp;
    }
    ll operator ()(ll x){
        return x - ((__int128(x) * m) >> 64) * p;
    }
} mod;

ll qp(ll x, ll y){
    ll ans = 1;
    while(y){
        if(y & 1){
            ans = mod(ans * x);
        }
        x = mod(x * x);
        y >>= 1;
    }
    return ans;
}

int main(){
    scanf("%d%lld", &T, &P);
    n = 1000;
    mod.init(P);
    C[0][0] = 1;
    for(int i = 1; i <= n; ++ i){
        C[i][0] = 1;
        for(int j = 1; j <= i; ++ j){
            C[i][j] = C[i-1][j] + C[i-1][j-1];
            if(C[i][j] >= P){
                C[i][j] -= P;
            }
        }
    }
    while(T--){
        ans = 0;
        scanf("%d%lld", &n, &m);
        for(int k = 0; k < n; ++ k){
            f[0][0] = 1;
            for(int i = 1; i <= n; ++ i){
                f[i][i/(k+1)+1] = 0;
                for(int j = 0; j * (k + 1) <= i; ++ j){
                    f[i][j] = mod(f[i-1][j] * (m - j));
                    if(i >= k + 1 && j){
                        ll tmp = mod(f[i-k-1][j-1] * (m - j + 1));
                        tmp = mod(tmp * C[n-(i-k)][k]);
                        f[i][j] -= tmp;
                        if(f[i][j] < 0){
                            f[i][j] += P;
                        }
                    }
                }
            }
            for(int j = 0; j * (k + 1) <= n; ++ j){
                ans += f[n][j];
                f[n][j] = 0;
                if(ans >= P){
                    ans -= P;
                }
            }
        }
        printf("%lld\n", mod(- ans + P + n * qp(m, n)));
    }
    return 0;
}