#include <cstdio>

int phi(int n)
{
	int n2=n,rez=n;
	
	for(int i=2;i*i<=n;i++)
		while(n2%i==0)
		{
			n2=n2/i;
			rez=rez/i*(i-1);
		}
	if(n2>1)
		return rez/n2*(n2-1);
	return rez;
}

int invers_modular(int a,int n)
{
	int p=phi(n)-1,rez=1;
	while(p)
	{
		if(p%2==1)
			rez=(rez*a)%n;
		a=(a*a)%n;
		p>>=1;
	}
	return rez;
}

int putere(int i,int x)
{
	int pow=0;
	while(i<=x)
	{
		pow+=x/i;
		i=i*i;
	}
	return pow;
}

int rezolv(long long A,long long B,int P)
{
	int a=1,b=1,c=1;
	int pa=putere(P,A),pb=putere(P,A-B),pc=putere(P,B);
	if(pa<pb+pc)
		return 0;

	
	for(long long i=1;i<=A;i++)
	{
		a=(a*i)%P;
		if(i<=B)
			b=(b*i)%P;
		if(i<=A-B)
			c=(c*i)%P;
		if(a==0 && b==0 && c==0)
			break;
	}
	
	return (a*invers_modular(b,P)*invers_modular(c,P))%P;
}

void citire_si_scriere()
{
	int P,Q;
	long long A,B;
	scanf("%d%d",&P,&Q);
	for(int i=1;i<=Q;i++)
	{
		scanf("%lld%lld",&A,&B);
		printf("%d\n",rezolv(A,B,P));
	}
}

int main()
{
	freopen("jap2.in","r",stdin);
	freopen("jap2.out","w",stdout);
	citire_si_scriere();
	
	return 0;
}