#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream fin("jap2.in");
ofstream fout("jap2.out");

ll P;
vector<ll> fact, inv_fact;

ll power(ll base, ll exp, ll mod) {
    ll result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

void precompute() {
    fact.resize(P);
    inv_fact.resize(P);
    fact[0] = 1;
    for (ll i = 1; i < P; i++)
        fact[i] = fact[i-1] * i % P;
    inv_fact[P-1] = power(fact[P-1], P-2, P); 
    for (ll i = P-2; i >= 0; i--)
        inv_fact[i] = inv_fact[i+1] * (i+1) % P;
}


ll combSmall(ll a, ll b) {
    if (b < 0 || b > a) return 0;
    return fact[a] % P * inv_fact[b] % P * inv_fact[a-b] % P;
}


ll lucas(ll a, ll b) {
    if (b == 0) return 1;
    return combSmall(a % P, b % P) * lucas(a / P, b / P) % P;
}

int main() {
    int q;
    fin >> P >> q;
    precompute();
    while (q--) {
        ll a, b;
        fin >> a >> b;
        fout << lucas(a, b) << '\n';
    }
    return 0;
}