#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll C[1005][1005],C2[1005],inv[1005],pw[1005],dp[1005][1005],mod;
const ll N=1000;

ll qkp(ll a,ll k) {
	ll ans=1;
	while (k) {
		if (k&1)ans*=a,ans%=mod;
		a*=a,a%=mod;
		k>>=1;
	}
	return ans;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
	ll T;
	cin >> T >> mod;
	C[0][0]=1;
	for (ll i=1; i<=N; i++) {
		C[i][0]=1;
		for (ll j=1; j<=N; j++) {
			C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
		}
	}
	while (T--) {
		ll n,m;
		cin >> n >> m;
		C2[0]=1;
		vector<ll> vct;
		for (ll i=1; i<=n; i++) {
			vct.push_back(m-i+1);
			ll z=i;
			for (ll &j:vct) {
				if (z==1)break;
				ll g=__gcd(j,z);
				j/=g,z/=g;
			}
			C2[i]=1;
			for (ll j:vct)C2[i]*=j,C2[i]%=mod;
		}
		ll ans=0;


		for (ll i=1; i<=n; i++) {
			dp[0][0]=1;
			for(ll j=0; j<=min(n/(i+1),m); j++) {
				pw[0]=1;
				for (ll k=1; k<=n; k++) {
					pw[i]=pw[i-1]*(m-j)%mod;
					dp[j][k]=(dp[j][k-1]*j%mod+(k>=i+1&&j?dp[j-1][k-i-1]*C[k-1][i]%mod*j%mod:0))%mod;
				}
				ll sm=0;
				for (ll i=1; i<=n; i++)
					for (ll k=0; k<=n; k++) {
						sm+=dp[j][k]*C[n][k]%mod*pw[n-k]%mod;
						if (sm>=mod)sm-=mod;
					}
				if (j&1) {
					ans-=sm*C2[j]%mod;
				} else {
					ans+=sm*C2[j]%mod;
				}
				if (ans<0)ans+=mod;
				if (ans>=mod)ans-=mod;
			}
//			cout<< ans<<"\n";
		}
		pw[0]=1;
		for (ll i=1; i<=n; i++)pw[i]=pw[i-1]*m%mod;
		cout<< ((n+1)*pw[n]%mod-ans+mod)%mod<<"\n";
	}
	return 0;
}

/*
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　■■■■■　　　　　■■　　　　　　■■■　　　　　■■■　　　■　　　　■　　　　　■　　　　　■■■■　　　　■■■■　　
　■　　　■■　　　　■■　　　　　■　　■■　　　■　　■■　　■　　　　■　　　　■■　　　　　■　　■■　　■■　　■　　
　■　　　　■　　　　■■　　　　■　　　　■　　■　　　　■　　　■　　■　　　　■■■　　　　■■　　■■　　■　　　■■　
　■　　　　■　　　　■■　　　　■　　　　■　　■　　　　■　　　■　　■　　　　　■■　　　　■　　　■■　　　　　　■■　
　■　　　　■　　　　■■　　　　■　　　　　　　■　　　　　　　　　■■　　　　　　■■　　　　　　　　■■　　　　　　■　　
　■　　　■■　　　　■■　　　　■　　■■■　　■　　■■■　　　　■■　　　　　　■■　　　　　　　■■　　　　　■■■　　
　■■■■■　　　　　■■　　　　■　　　　■　　■　　　　■　　　　■■　　　　　　■■　　　　　　■■　　　　　　　　■■　
　■　　　　　　　　　■■　　　　■　　　　■　　■　　　　■　　　　■■　　　　　　■■　　　　　■■　　　　　　　　　　■　
　■　　　　　　　　　■■　　　　■　　　　■　　■　　　　■　　　　■■　　　　　　■■　　　　　■　　　　　　■　　　■■　
　■　　　　　　　　　■■　　　　■■　　■■　　■■　　■■　　　　■■　　　　　　■■　　　　■　　　　　　　■■　　■■　
　■　　　　　　　　　■■　　　　　　■■■■　　　　■■■■　　　　■■　　　　　　■■　　　　■■■■■■　　　■■■■　　
*/