#include<iostream>
#include<map>
using namespace std;
const int N=1e3+5;
map<int,int>f[N],vis[N];
int mod,C[N][N];
void init(){for(int i=0;i<N;++i)for(int j=C[i][0]=1;j<=i;++j)C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;}
int get(int i,int j,int k)
{
	if(i<0)return 0;
	if(i==0)return 1;
	if(vis[i].count(j)&&vis[i][j]==k)return f[i][j];
	vis[i][j]=k,f[i][j]=1ll*j*get(i-1,j,k)%mod;
	return f[i][j]=(f[i][j]-1ll*C[i-1][k]*get(i-1-k,j-1,k)%mod*j%mod+mod)%mod;
}
void ATRI()
{
	int n,m;cin>>n>>m;
	int ans=n;
	for(int i=1;i<=n;++i)ans=1ll*ans*m%mod,vis[i].clear();;
	for(int k=0;k<n;++k)ans=(ans-get(n,m,k)+mod)%mod;
	cout<<ans<<"\n";
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int t;cin>>t>>mod;init();while(t--)ATRI();
	return 0;
}