/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

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

ifstream fin("jap2.in");
ofstream fout("jap2.out");


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

long long exp_log(long long x, long long n, int mod) {
    if (n == 0)
        return 1;
    long long p = 1;
    x = x % mod;
    while (n > 0) {
        if (n % 2)
            p = (p * x) % mod;
        x = (x * x) % mod;
        n /= 2;
    }
    return p;
}

int main()
{
    
    int p,q;
    fin>>p>>q;
	while(q){
        long long n, k;
	    fin>>n>>k;
	    long long nfact=1, kfact=1, nminusk=1;
	    for(long long i=2;i<=n;i++)
	        nfact*=(i % p);
	    for(long long i = 2;i<=k;i++)
            kfact*=(i % p);
        for(long long i=2;i<=(n-k);i++)
            nminusk*=(i % p);
        
        kfact = exp_log(kfact,phi(p)-1,p);
        nminusk = exp_log(nminusk,phi(p)-1,p);
        
        fout<< (nfact * kfact * nminusk) % p<<endl;
        
	    q--;
	 }

	return 0;
}