#include <fstream>
using namespace std;
ifstream in("jap2.in");
ofstream out("jap2.out");
typedef long long ll;

void gcd(ll a,ll b,ll &x,ll &y)
{
	if (!b)
	{
		x = 1;
		y = 0;
	}
	else
	{
		ll x0, y0;
		gcd(b,a%b,x0,y0);
		x = y0;
		y = x0 - y0 * (a / b);
	}
}

int inversmodular(ll A, ll N)
{
	ll x, y;
	gcd(A, N, x, y);
	if (x <= 0) x += N;
	return x;
}

int main()
{
	ll p, n, a, b;
	in >> p >> n;
	while (n)
	{
		ll fact1, fact2, factn, ftemp=1;
		in >> a >> b;
		if (a - b == 0) fact2 = 1;
		for (int i = 1; i <= a; i++)
		{
			ftemp *= i;
			ftemp %= p;
			if (i == b) fact1 = ftemp;
			if (i == a - b) fact2 = ftemp;
		}
		factn = ftemp;
		out << factn * inversmodular(fact1, p)*inversmodular(fact2, p)%p<<'\n';
		n--;
	}
}