#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 int operator%(int x,const BR &y){return y(x);}
	friend int &operator%=(int &x,const BR &y){return x=y(x);}
	friend long long operator%(long long x,const BR &y){return y(x);}
	friend long long &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<=n/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;
			}
		}
		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;
	}
	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();
}