#if defined(_USE_PCH_)
#include "pch.hpp"
#else
#include <bits/stdc++.h>
#endif
#define RNG(V_, A_, B_, ...) for(int V_=(A_), V_##_END=(B_) __VA_OPT__(,) __VA_ARGS__; V_<=V_##_END; V_++)
#define IRNG(V_, A_, B_, ...) for(int V_=(A_), V_##_END=(B_) __VA_OPT__(,) __VA_ARGS__; V_>=V_##_END; V_--)
#ifdef _WIN32
#define long int64_t
#endif
#define fi first
#define se second
#define _UN using namespace
using namespace std;
typedef pair<int,int> pii;
typedef __int128 i128;
namespace std{
    template<>
    struct hash<pair<int,int>>{
        size_t operator()(const pair<int,int>& x)const{ return _Hash_bytes(&x,sizeof(x),0xc70f6907); }
    };
}
const int MAXN=1010; const long NINF=0xc0c0c0c0c0c0c0c0;
int mod,fac[MAXN],inv[MAXN],n,m;
long C[MAXN][MAXN];
long F[MAXN][MAXN];
long solve(int k){
    if(k==0) return 0;
    RNG(j,max(1,m-n/(k+1)-1),m){
        F[0][m-j]=1;
        RNG(i,1,n) F[i][m-j]=j*(F[i-1][m-j]-(i-1-k<0||j-1<=0?0:F[i-1-k][m-(j-1)])*C[i-1][k]%mod)%mod;
    }
    return F[n][m-m];
}
void case_main(){
    cin>>n>>m;
    RNG(i,1,n) fill(F[i],F[i]+n+1,0);
    long ans=0,sum=1;
    RNG(_,1,n) sum=sum*m%mod;
    IRNG(k,n,1){
        auto x=solve(k-1);
        ans=(ans+(sum-x+mod)*k)%mod;
        sum=x;
    }
    cout<<ans<<"\n";
}
int main(){
#if defined(_LOCAL_)
    freopen("in","r",stdin);
//  freopen("out","w",stdout);
//  freopen("/dev/null","w",stderr);
#else
//  freopen("yesterday.in","r",stdin);
//  freopen("yesterday.out","w",stdout);
#endif
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    int cas; cin>>cas>>mod;
    auto N=1000;
    C[0][0]=1;
    RNG(i,1,N){
        C[i][0]=1;
        RNG(j,1,i) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
    }
    RNG(_,1,cas) case_main();
}