#include <stdio.h>
#include <stdlib.h>

#define in "jap2.in"
#define out "jap2.out"

void euclid_extins(long long a, long long b, long long *x, long long *y)
{
    if (b == 0)
    {
        *x = 1;
        *y = 1;
    }
    else
    {
        long long x1, y1;
        euclid_extins(b, a % b, &x1, &y1);
        *x = y1;
        *y = x1 - a / b * y1;
    }
}

int main()
{
    FILE *fin, *fout;
    fin = fopen(in, "r");
    fout = fopen(out, "w");

    long long P, Q, A, B;
    long long factorial[100007];

    fscanf(fin, "%lld %lld", &P, &Q);

    factorial[0] = 1;

    for (int i = 1; i < 100007; i++)
    {
        factorial[i] = (factorial[i - 1] * i) % P;
    }

    for (int i = 1; i <= Q; i++)
    {
        fscanf(fin, "%lld %lld", &A, &B);
        long long result, a, b, c, temp; // a -> N!, b -> (K!)^-1, c ->(N-K)!^-1
        a = factorial[A];
        euclid_extins(factorial[B], P, &b, &temp);
        if (b <= 0)
        {
            b = P + b % P;
        }
        euclid_extins(factorial[A - B], P, &c, &temp);
        if (c <= 0)
        {
            c = P + c % P;
        }
        result = a * b * c;
        fprintf(fout, "%lld\n", result % P);
    }

    fclose(fin);
    fclose(fout);
    return 0;
}