#include <fstream>
#include <cstdio>
using namespace std;

long long p;
long long sus[1<<17],jos[1<<17];

ifstream in("jap2.in");

long long fact(long long n,long long x)
{
	long long nr=0;
	while (n)
	{
		nr+=n/x;
		n/=x;
	}
	return nr;
}

long long power(long long x,long long n)
{
	if (!n)
		return 1;
	if (n==1)
		return x%p;
	return power(x*x%p,n>>1)*power(x,n&1)%p;
}

inline void factorise(long long &s,long long v[],long long a)
{
	s=s*power(v[p-1],a/p+a/p/p)%p;
	s=s*v[a%p]*v[a/p%p]%p; 
}

inline long long comb(long long a,long long b)
{
	long long s=1;
	factorise(s,sus,a);
	factorise(s,jos,b);
	factorise(s,jos,a-b);
	return s;
}	

inline long long inv(long long x)
{
	return power(x,p-2);
}

int main()
{
	long long t,a,b,i;
	in>>p>>t;
	sus[0]=jos[0]=1;
	for (i=1;i<p;i++)
	{
		sus[i]=sus[i-1]*i%p;
		jos[i]=jos[i-1]*inv(i)%p;
	}
	freopen("jap2.out","w",stdout);
	while (t--)
	{
		in>>a>>b;
		if (fact(a,p)-fact(b,p)-fact(a-b,p)>0)
		{
			printf("0\n");
			continue;
		}
		printf("%lld\n",comb(a,b));
	}
	return 0;
}