#include<stdio.h>
#include<algorithm>
#define M 1005
using namespace std;
int n,m,T,C[M][M];
struct BR{
	typedef unsigned long long ull;
	ull p,m;
	BR():m{2}{p=-m/m+1;}
	BR(int mod):m{(ull)mod}{p=-m/m+1;};
	inline ull operator()(ull x) const{
		if((x-=ull((unsigned __int128)x*p>>64)*m)>=m) x-=m;
		return x;
	}
	operator int() const{return m;}
	friend operator%(int x,const BR &y){return y(x);}
	friend operator%=(int &x,const BR &y){return x=y(x);}
	friend operator%(long long x,const BR &y){return y(x);}
	friend operator%=(long long &x,const BR &y){return x=y(x);}
} mod;
int f[M][M],g[M];
inline void solve(){
	scanf("%d%d",&n,&m);
	for(int k=1;k<=n;++k){
		f[0][0]=1;
		for(int i=1;i<=n;++i){
			f[i][i/k+1]=0;
			for(int j=0;j<=i/k;++j){
				f[i][j]=1ll*(m-j)*f[i-1][j]%mod;
				if(j&&i>k) (f[i][j]+=1ll*(m-j+1)*C[n-i+k][k]%mod*f[i-k-1][j-1])%=mod;
				// printf("%d %d: %d\n",i,j,f[i][j]);
			}
		}
		long long s=0;
		for(int i=0;i<=n/k;++i) s+=i&1?mod-f[n][i]:f[n][i];
		g[k]=s%mod;
		// printf("%d %d %d: %lld\n",n,m,k,s);
	}
	for(int i=n;i;--i) g[i]=(g[i]+mod-g[i-1])%mod;
	long long s=0;
	for(int i=1;i<=n;++i) (s+=1ll*g[i]*i%mod)%=mod;
	printf("%lld\n",s);
}
int main(){
	// freopen("in.txt","r",stdin);
	int T,p;scanf("%d%d",&T,&p),mod=BR(p);
	for(int i=0;i<M;++i){
		C[i][0]=1;
		for(int j=1;j<=i;++j) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
	}
	while(T--) solve();
}

answer.code:16:16: error: ISO C++ forbids declaration of ‘operator%’ with no type [-fpermissive]
   16 |         friend operator%(int x,const BR &y){return y(x);}
      |                ^~~~~~~~
answer.code:17:16: error: ISO C++ forbids declaration of ‘operator%=’ with no type [-fpermissive]
   17 |         friend operator%=(int &x,const BR &y){return x=y(x);}
      |                ^~~~~~~~
answer.code:18:16: error: ISO C++ forbids declaration of ‘operator%’ with no type [-fpermissive]
   18 |         friend operator%(long long x,const BR &y){return y(x);}
      |                ^~~~~~~~
answer.code:19:16: error: ISO C++ forbids declaration of ‘operator%=’ with no type [-fpermissive]
   19 |         friend operator%=(long long &x,const BR &y){return x=y(x);}
      |                ^~~~~~~~
answer.code: In function ‘int main()’:
answer.code:46:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   46 |         int T,p;scanf("%d%d",&T,&p),mod=BR(p);
      |                 ~~~~~^~~~~~~~~~~~~~
answer.code: In function ‘void solve()’:
answer.code:23:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   23 |         scanf("%d%d",&n,&m);
      |         ~~~~~^~~~~~~~~~~~~~