#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 1005, S = 32;
int f[N][N], g[N][N], A[N][N], B[N][N], fac[N], inv[N], iv[N], mod;
int C[N][N];
int pw[N];
int qpow(int x, int y)
{
	int ans = 1;
	while(y)
	{
		if(y & 1)
			ans = (ll)ans * x % mod;
		x = (ll)x * x % mod;
		y >>= 1;
	}
	return ans;
}
int exgcd(int &x, int &y, int a, int b)
{
	if(!a)
	{
		x = 0;
		y = 1;
		return b;
	}
	int g = exgcd(y, x, b % a, a);
	x -= (b / a) * y;
	return g;
}
void prep(int n)
{
	int i, j, k, l;
	// fac[0] = 1;
	// for(i = 1; i <= n; i++)
	// 	fac[i] = (ll)fac[i - 1] * i % mod;
	// inv[n] = qpow(fac[n], mod - 2);
	// for(i = n; i >= 1; i--)
	// 	inv[i - 1] = (ll)inv[i] * i % mod;
	// for(i = 1; i <= n; i++)
	// 	iv[i] = (ll)inv[i] * fac[i - 1] % mod;
	for(i = 0; i <= n; i++)
	{
		C[i][0] = 1;
		for(j = 1; j <= i; j++)
			C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
	}
	for(i = 1; i <= S; i++)
	{
		f[0][0] = 1;
		for(j = 1; j <= n; j++)
			for(k = 0; k < n; k++)
				f[j][k + 1] = (f[j][k] + f[j - 1][k] + (k < i ? 0ll : (ll)(mod - C[k][i]) * f[j - 1][k - i])) % mod * j % mod;
		// if(i == 2)
		// 	printf("??%d\n", f[2][3]);
		for(j = 0; j <= n; j++)
			for(k = 0; k <= n; k++)
				A[k][j] = (A[k][j] + (ll)((i == S) ? S : mod - 1) * f[j][k]) % mod;
		if(i == S)
			for(j = 0; j <= n; j++)
				for(k = 0; k <= n; k++)
					B[k][j] = f[j][k];
	}
	// for(j = 0; j <= n; j++)
	// 	for(k = 0; k <= n; k++)
	// 	{
	// 		A[j][k] = (ll)A[j][k] * inv[k] % mod;
	// 		B[j][k] = (ll)B[j][k] * inv[k] % mod;
	// 	}
	memset(f, 0, sizeof(f));
	for(i = n; i > S; i--)
	{
		for(j = 0; j <= n; j++)
			for(k = 0; k <= j / i; k++)
				g[j][k] = 0;
		pw[0] = 1;
		for(j = 1; j <= n / i; j++)
			pw[j] = (ll)pw[j - 1] * C[j * i][i] % mod;
		f[0][0] = i;
		for(j = 0; j <= n; j++)
			for(k = 0; k <= j / i; k++)
				for(l = 0; l <= (n - j) / i; l++)
					g[j + l * i][k + l] = (g[j + l * i][k + l] + (ll)f[j][k] * pw[l] % mod * C[j + l * i][j] % mod * C[k + l][k]) % mod;
		g[0][0] = 0;
		for(j = 0; j <= n; j++)
			for(k = 0; k <= j / i; k++)
				f[j][k] = g[j][k];
	}
}
int pr[105], pp[105], ct[105], cnt;
void work(int m)
{
	int i;
	for(i = 2; i * i <= m; i++)
		if(!(m % i))
		{
			++cnt;
			pr[cnt] = i;
			while(!(m % i))
			{
				m /= i;
				pp[cnt]++;
			}
		}
	if(m > 1)
	{
		++cnt;
		pr[cnt] = m;
		pp[cnt] = 1;
	}
}
int qwq(int x, int y)
{
	int i;
	for(i = 1; i <= cnt; i++)
		while(!(x % pr[i]))
		{
			ct[i] += y;
			x /= pr[i];
		}
	return x;
}

int main()
{
	int i, j, k, T, n, m, ans, v, x, y;
	scanf("%d%d", &T, &mod);
	prep(1000);
	work(mod);
	while(T--)
	{
		scanf("%d%d", &n, &m);
		memset(pw, 0, sizeof(pw));
		pw[0] = v = 1;
		ans = 0;
		for(j = 1; j <= cnt; j++)
			ct[j] = 0;
		for(i = 0; i < min(n, m); i++)
		{
			v = (ll)v * qwq(m - i, 1) % mod;
			exgcd(x, y, qwq(i + 1, -1), mod);
			v = (ll)(x + mod) * v % mod;
			pw[i + 1] = v;
			for(j = 1; j <= cnt; j++)
				for(k = 1; k <= min(pp[j], ct[j]); k++)
					pw[i + 1] = (ll)pw[i + 1] * pr[j] % mod;
		}
		for(i = 0; i <= n; i++)
		{
			// printf("!%d %d\n", i, pw[i]);
			ans = (ans + (ll)A[n][i] * pw[i]) % mod;
			// printf("??%d %d\n", i, A[n][i]);
			for(j = 0; j <= i; j++)
				for(k = 0; k <= (n - i) / S; k++)
					ans = (ans + (ll)B[i][j] * f[n - i][k] % mod * C[j + k][j] % mod * C[n][i] % mod * pw[j + k]) % mod;
		}
		printf("%d\n", ans);
	}
	return 0;
}