#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ulll __uint128_t
#define mod FM.reduce
const int N=1e3+5;
int T,MOD,n,m,ans,bn[N][N],dp[N][N];
struct FastMod
{
	ull p,w;FastMod(ull p=2):p(p),w((ull)(((ulll)(1)<<64)/p)) {}
    ull reduce(ull x) {ull d=(ull)(((ulll)(w)*x)>>64),r=x-p*d;return r>=p?r-p:r;}
}FM;
void W(int &x,int y) {x+=y;if(x>=MOD) x-=MOD;}
void W(int &x,ll y) {x=(x+y)%MOD;}
int qpow(int x,int y)
{
	int res=1;
	for(;y;y/=2,x=mod(1ll*x*x)) if(y&1)
		res=mod(res*x);return res;
}
void init(int n)
{
	for(int i=0;i<=n;++i) for(int j=0;j<=i;++j)
		bn[i][j]=j?mod(bn[i-1][j]+bn[i-1][j-1]):1;
}
int calc(int x)
{
	int res=0;dp[0][0]=1;
	for(int i=1;i<=n;++i)
	{
		dp[i][i/x+1]=0;
		for(int j=0;j*x<=i;++j)
			dp[i][j]=mod(1ll*dp[i-1][j]*(m-j)+(i>=x && j?mod(1ll*dp[i-x][j-1]*(m-j+1))*bn[n-i+x-1][x-1]:0));
	}
	for(int i=0;i*x<=n;++i) W(res,i&1?MOD-dp[n][i]:dp[n][i]);return res;
}
void slv()
{
	scanf("%d %d",&n,&m);ans=mod(1ll*qpow(m,n)*n);
	for(int i=1;i<=n;++i) W(ans,MOD-calc(i));printf("%d\n",ans);
}
int main()
{
	scanf("%d %d",&T,&MOD);FM=FastMod(MOD);
	init(1e3);while(T--) slv();return 0;
}