#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;
}

In file included from /usr/include/c++/13/string:43,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from answer.code:3:
/usr/include/c++/13/bits/allocator.h: In destructor ‘std::_Vector_base<long long int, std::allocator<long long int> >::_Vector_impl::~_Vector_impl()’:
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = long long int]’: target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/13/vector:66,
                 from /usr/include/c++/13/queue:63,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:157:
/usr/include/c++/13/bits/stl_vector.h:133:14: note: called from here
  133 |       struct _Vector_impl
      |              ^~~~~~~~~~~~