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

const int N = 1e3 + 10;
int T, mod, C[N][N];
unordered_map<int,int> q[N];

ll quick_pow(ll x, int y){
	ll res = 1;
	while(y){
		if(y & 1) res = res * x % mod;
		x = x * x % mod;
		y >>= 1;
	}
	return res;
}

void pre(){
	C[0][0] = 1;
	for(int i = 1; i < N; ++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;
	}
	return;
}

int dfs(int x, int y, int lim){
	if(x < 0 || !lim) return 0;
	if(x == 0) return 1;
	if(x == 1) return y;
	if(q[x].find(y) != q[x].end()) return q[x][y];
	return q[x][y] = (1ll * y * dfs(x - 1, y, lim) % mod - 1ll * dfs(x - lim - 1, y - 1, lim) * C[x - 1][lim] % mod * y % mod + mod) % mod;
}

signed main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	// int st = clock();
	cin >> T >> mod;
	pre();
	while(T--){
		int n, m;
		scanf("%d%d", &n, &m);
		ll res = 0, S = quick_pow(m, n);
		for(int i = 0; i <= n; ++i){
			for(int j = 0; j <= n; ++j){
				auto it = q[j].begin();
				while(it != q[j].end()) it = q[j].erase(it);
			}
			res = (res + S - dfs(n, m, i) % mod) % mod;
		}
		printf("%lld\n", (res + mod) % mod);
	}
	// int en = clock();
	// cerr << en - st << '\n';
	return 0;
}
/*
3 123456789
3 2
5 5
7 7
*/