#include <iostream>
#include <fstream>

using namespace std;

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

typedef long long ll;

ll modulo;

ll fact(ll n){
  int ans = 1;
  for(int i = 1;i <= n;i++){
    ans = (ans * i) % modulo;
  }
  return ans;
}

ll logpow(ll val, ll pow, ll left){
  if(pow == 1){
    return (val * left) % modulo;
  }else if(pow % 2 == 0){
    return logpow((val * val) % modulo, pow / 2, left);
  }else{
    return logpow((val * val) % modulo, (pow - 1) / 2, (left * val) % modulo);
  }
}

ll InvMod(ll n){
  return logpow(n, modulo-2, 1);
}

int main()
{
  ll n, a, b, facta, factb, factab;
  in >> modulo >> n;
  for(int i = 1;i <= n;i++){
    in >> a >> b;
    facta = fact(a);
    factb = fact(b);
    factab = fact(a-b);
    out << facta * InvMod((factb * factab) % modulo)%modulo << '\n';
  }
  return 0;
}