#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];
unordered_map<pair<int,int>,long> mp;
long dfs(int i,int j,int k){
    if(i==0) return 1;
    if(i<0||j<=0||1l*j*k<i) return 0;
    if(auto it=mp.find({i,j}); it!=mp.end()) return it->se;
    auto ret=j*(dfs(i-1,j,k)-dfs(i-1-k,j-1,k)*C[i-1][k])%mod;
    assert(ret>=0);
    return mp[{i,j}]=ret;
}
long solve(int k){
    if(k==0) return 0;
    mp.clear();
    return dfs(n,m,k);
}
void case_main(){
    cin>>n>>m;
    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();
}