#include <bits/stdc++.h>
#define ll long long
#pragma GCC optimize(2,3,"Ofast","unroll-loops")
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++) {
				pw[0]=1;
				for (ll k=1; k<=n; k++) {
					pw[k]=mod(pw[k-1]*(m-j));
					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;
				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]);
					if (ans<0)ans+=MM;
				} else {
					ans+=mod(sm*C2[j]);
					if (ans>=MM)ans-=MM;
				}
//				cout<<"!"<<sm<< endl;
			}
//			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;
}

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