#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() {
	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++){
				for (ll k=1;k<=n;k++){
					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;
				pw[0]=1;
				for (ll i=1;i<=n;i++)pw[i]=pw[i-1]*(m-j)%mod;
				for (ll k=0;k<=n;k++){
					sm+=dp[j][k]*C[n][k]%mod*pw[n-k]%mod;
					sm%=mod;
				}
				if (j&1){
					ans-=sm*C2[j]%mod;
				}else{
					ans+=sm*C2[j]%mod;
				}
//				cout<<"!"<<sm<< endl;
				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;
}

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