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

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

struct Mod
{
    ll m, p;
    void init(int pp) { m = ((__int128)1 << 64) / pp; p = pp; }
    ll operator ()(ll x)
    {
        return x - ((__int128(x) * m) >> 64) * p;
    }
} mod;

int main() {
	cin.tie(0);cout.tie(0);
	ios::sync_with_stdio(false);
	ll T;
	cin >> T >> MM;
	mod.init(MM);
	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]=mod(C[i-1][j]+C[i-1][j-1]);
		}
	}
	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(C2[i]);
		}
		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]=mod(mod(dp[j][k-1]*j)+mod(k>=i+1&&j?mod(dp[j-1][k-i-1]*C[k-1][i])*j:0));
				}
				ll sm=0;
				pw[0]=1;
				for (ll i=1;i<=n;i++)pw[i]=mod(pw[i-1]*(m-j));
				for (ll k=0;k<=n;k++){
					sm+=mod(mod(dp[j][k]*C[n][k])*pw[n-k]);
					if (sm>=MM)sm-=MM;
				}
				if (j&1){
					ans-=mod(sm*C2[j]);
				}else{
					ans+=mod(sm*C2[j]);
				}
//				cout<<"!"<<sm<< endl;
				ans%=MM;
				ans+=MM;
				if(ans>=MM)ans-=MM;
				if(ans>=MM)ans-=MM;
			}
//			cout<< ans<<"\n";
		}
		pw[0]=1;
		for (ll i=1;i<=n;i++)pw[i]=mod(pw[i-1]*m);
		cout<< mod(mod((n+1)*pw[n])-ans+MM)%MM<<"\n";
	}
	return 0;
}

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