#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#pragma GCC optimize("Ofast","unroll-loops","inline")
#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define R(i, x, y) for (int i = (x); i >= (y); i--)
#define FIO(FILE) freopen(FILE".in", "r", stdin), freopen(FILE".out", "w", stdout)
#define int long long
using namespace std;
typedef long long ll;
typedef vector<int> arr;
typedef pair<int, int> pi;
bool Mbe;
const int N = 1e3 + 5;
int n, M, P;
int C[N][N], f[N][N];
arr conq(int M) {
if (!M) {
arr res(n + 1, 0);
res[0] = 1;
return res;
}
arr res(n + 1, 0), tp = conq(M >> 1);
F (i, 0, n) F (j, 0, n - i) res[i + j] += tp[i] * tp[j] % P;
F (i, 0, n) res[i] %= P;
if (M & 1) R(i, n, 1) (res[i] += res[i - 1]) %= P;
return res;
}
void init(int lim) {
C[0][0] = 1;
F (i, 1, lim) {
C[i][0] = 1;
F (j, 1, i) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % P;
}
}
void solve() {
cin >> n >> M;
arr cp = conq(M);
int ans = 0;
F (i, 1, n) {
F (m, 1, min(M, n / i)) F (k, 1, n) f[m][k] = 0;
f[0][0] = 1;
F (m, 1, min(M, n / i)) F (k, i * m, n)
f[m][k] = (f[m][k - 1] + f[m - 1][k - i] * C[k - 1][i - 1]) % P * m % P;
F (m, 1, min(M, n / i)) {
int pw = 1, s = 0;
R (k, n, i * m) {
s += pw * C[n][k] % P * f[m][k] % P;
pw = pw * (M - m) % P;
}
s %= P;
if ((m - 1) & 1) ans -= s * cp[m] % P;
else ans += s * cp[m] % P;
}
}
cout << ans % P << '\n';
}
bool Med;
signed main() {
// FIO("");
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cerr << (&Mbe - &Med) / 1048576.0 << " MB\n";
int T = 1;
cin >> T >> P, init(1e3);
while (T--) solve();
cerr << (int)(1e3 * clock() / CLOCKS_PER_SEC) << " ms\n";
return 0;
}