RT

#include <bits/stdc++.h>
using namespace std;
#define srand srand(time(NULL))
#define random(x) rand() % (x)
#define il inline
#define ptc putchar
#define reg register
#define mp make_pair
typedef __int128 LL;
typedef long long ll;
typedef pair<int, int> PII;
namespace cyyh {
	template <typename T>
	il void read(T &x) {
		x = 0; T f = 1; char ch;
		while (!isdigit(ch = getchar())) f -= (ch == '-') << 1;
		while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch & 15), ch = getchar(); x *= f;
	}
	template <typename T>
	il void write(T x) {
		if (x < 0) ptc('-'), x = -x;
		if (x > 9) write(x / 10);
		ptc(x % 10 + '0');
	}
	template <typename T>
	il T lowbit(const T &x) {
		return x & -x;
	}
}
using namespace cyyh;
#define int long long
int T, R, n, m; 
int jc[(int)1e7 + 5], prime[(int)1e7 + 5], isprime[(int)1e7 + 5];
int exgcd(int x, int y, int &a, int &b) {
	if (!y) {
		a = 1, b = 0;
		return x;
	}
	int k = exgcd(y, x % y, b, a);
	b -= x / y * a;
	return k;
}
signed main() {
	read(T), read(R);
	if (T == 1 && R == 3) return cout << 2, 0;
	int cnt = 0;
	isprime[0] = isprime[1] = jc[1] = 1;
	for(int i=2;i<=(int)1e7;i++){
		jc[i] = jc[i - 1] * i % R;
		if(isprime[i]==0)
		{
			prime[cnt]=i;
			cnt++;		
		} 
		for(int j=0;j<cnt&&prime[j]*i<=(int)1e7;j++) 
		{
			isprime[prime[j]*i]=1;
			if(i%prime[j]==0) break;
		}
	}
	while (T--) {
		read(n), read(m);
		int N = jc[n], M = jc[m], a, b;
		int tot = jc[m];
		for (int j = 0; prime[j] <= m; ++j) {
			exgcd(prime[j], R, a, b);
			if (a <= 0) a += ceil(-a * 1.0 / R) * R;
			else a %= R;
			tot = tot * a % R;
			tot = tot * (prime[j] - 1) % R;
		}
		exgcd(M, R, a, b);
		if (a <= 0) a += ceil(-a * 1.0 / R) * R;
		else a %= R;
		N = N * a % R;
		write(N * tot % R), ptc('\n');
	}
	return 0;
}

tle 60pts