组合数与递推

// 标准答案 —— 杨辉三角递推：**C(n,k) = C(n−1,k−1) + C(n−1,k)**
//
// ★ 这条递推为什么成立（一句话，而且是这一章的地基）：
//   从 n 个东西里挑 k 个，盯住**第 n 个东西**：
//     · 挑它 ⇒ 剩下的从前 n−1 个里挑 k−1 个 ⇒ C(n−1, k−1)；
//     · 不挑它 ⇒ 从前 n−1 个里挑 k 个 ⇒ C(n−1, k)。
//   两类不重不漏，加起来就是全部。∎
//   ⚠ 注意它**全程只有加法** —— 于是「取模」这件事在这里毫无难度（加完取一次就行）。
//     第 6 步会看到：正解那条路是乘法和除法，取模的坑全在那边。
//
// 为什么它存在：
//   ① 它是对拍里的标准答案，想法和「阶乘 + 逆元」**完全不同**
//      （一个是递推，一个是公式；第 9、15 章那条规矩）；
//   ② ★ 它同时是这一章的反面教材：要 O(n²) 的时间和空间 ——
//      n = 10⁶ 时那张表有 10¹² 个格子，**开都开不出来**。
//
// ⚠ 边界（题面写死的，也是这一章两个 bug 的落点）：
//   · C(n, 0) = C(n, n) = 1；
//   · **k > n 时 C(n,k) = 0**。
//
// 复杂度 O(n²)。

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll p;
    int q;
    if (!(cin >> p >> q)) return 0;

    vector<pair<int, int>> qs(q);
    int maxn = 0;
    for (auto& [n, k] : qs) { cin >> n >> k; maxn = max(maxn, n); }

    // 杨辉三角：一行一行往下推
    vector<vector<ll>> c(maxn + 1);
    for (int i = 0; i <= maxn; i++) {
        c[i].assign(i + 1, 0);
        c[i][0] = 1 % p;
        for (int j = 1; j <= i; j++)
            c[i][j] = (c[i - 1][j - 1] + (j <= i - 1 ? c[i - 1][j] : 0)) % p;
    }

    string out;
    int zeros = 0;
    for (auto& [n, k] : qs) {
        ll v = (k > n) ? 0 : c[n][k];              // ⚠ k > n 时是 0
        if (v == 0) zeros++;
        out += to_string(v);
        out += '\n';
    }
    out += to_string(zeros);                       // ★ 末行：答案是 0 的有几组
    out += '\n';

    cout << out;
    return 0;
}

// 正解 —— 阶乘 + 乘法逆元：**C(n,k) = n! · (k!)⁻¹ · ((n−k)!)⁻¹ (mod p)**
//
// ============ ★ 关键一步：除法在模意义下怎么做 ============
//
//   `C(n,k) = n! / (k! · (n−k)!)`。可**取模之下不能直接除** ——
//   `(a / b) mod p` 和 `(a mod p) / (b mod p)` 根本不是一回事。
//
//   ★ 办法是把「除以 b」换成「乘以 b 的**逆元**」：
//     **b⁻¹ 是那个满足 `b · b⁻¹ ≡ 1 (mod p)` 的数。**
//
//   而这个逆元存在的**充要条件**是 `gcd(b, p) = 1`（第 40 章的裴蜀定理：
//   `b·x + p·y = 1` 有整数解 ⟺ `gcd(b,p) | 1`）。
//   ⇒ **p 是质数**的时候，只要 b 不是 p 的倍数就一定有逆元。
//
//   怎么求？**费马小定理**（第 42 章 verify.cpp 验过的那条）：
//     p 是质数、b 不是 p 的倍数 ⇒ `b^(p−1) ≡ 1` ⇒ **`b⁻¹ ≡ b^(p−2)`**。
//   ⚠ 是 **p−2**，不是 p−1 —— 差一个数，答案就恒等于 1。
//   于是逆元 = 一次快速幂（第 42 章那五行原样搬过来）。
//
// ============ ★ 这一章串起了前面三章 ============
//
//   · 第 40 章：逆元存在 ⟺ gcd = 1（裴蜀定理）；
//   · 第 41 章：p 得是**质数**，费马小定理才成立；
//   · 第 42 章：算 `b^(p−2)` 靠**快速幂**。
//   ⇒ 数学这一块四章，到这里正好收口。
//
// ⚠⚠ 而这套办法有一个必须写明的前提：**p 必须大于 n**。
//   否则 `n!` 里含有 p 这个因子 ⇒ `n! ≡ 0`，而 0 没有逆元，整套公式当场失效
//   （smallP.cpp 把这件事跑出来给你看，正解是 Lucas 定理 —— 这一章只点到为止）。
//   所以题面写的是 `10⁶ < p ≤ 10⁹` 而 `n ≤ 10⁶`。
//
// ============ ★ 逆元阶乘的那个倒推，值得单独看一眼 ============
//
//   一个个求 `(i!)⁻¹` 要 n 次快速幂（O(n log p)）。其实只要**一次**：
//     先求 `(n!)⁻¹`，然后 **`((i−1)!)⁻¹ = (i!)⁻¹ · i`** —— 从大往小倒着推。
//   （因为 `(i−1)! = i! / i`，取逆元就是乘 i。）
//   ⇒ 预处理 O(n + log p)，每次询问 O(1)。
//
// 复杂度 O(n + log p + q)。

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using i128 = __int128;

ll p;

/** 快速幂 —— 第 42 章那五行 */
ll power(ll a, ll b) {
    ll res = 1 % p;
    a %= p;
    if (a < 0) a += p;
    while (b) {
        if (b & 1) res = (i128)res * a % p;
        a = (i128)a * a % p;
        b >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    if (!(cin >> p >> q)) return 0;

    vector<pair<int, int>> qs(q);
    int maxn = 0;
    for (auto& [n, k] : qs) { cin >> n >> k; maxn = max(maxn, n); }

    vector<ll> fac(maxn + 1), inv(maxn + 1);
    fac[0] = 1 % p;
    for (int i = 1; i <= maxn; i++) fac[i] = (i128)fac[i - 1] * i % p;

    inv[maxn] = power(fac[maxn], p - 2);           // ⚠ 是 p−2，不是 p−1
    for (int i = maxn; i >= 1; i--)                // ★ 从大往小倒推，只要一次快速幂
        inv[i - 1] = (i128)inv[i] * i % p;

    string out;
    int zeros = 0;
    for (auto& [n, k] : qs) {
        ll v;
        if (k > n) v = 0;                          // ⚠ k > n 时是 0
        else v = (ll)((i128)fac[n] * inv[k] % p * inv[n - k] % p);
        if (v == 0) zeros++;
        out += to_string(v);
        out += '\n';
    }
    out += to_string(zeros);                       // ★ 末行：答案是 0 的有几组
    out += '\n';

    cout << out;
    return 0;
}

// ⚠⚠ 这不是错误版本 —— `fac[0]` 写成 1 而不是 `1 % p`，而它在这一章**完全无害**。
//
//   和第 42 章那个 `res = 1 % p` 是同一个坑 —— 只是这一章的 p 保证 > 10⁶，
//   所以 `1 % p` 恒等于 1……
//
// ⚠⚠ **于是这份代码其实是对的**：它 300 轮和正解逐字节相同。
//   ★ 留着它是为了说一件事：**同一个手滑，在第 42 章是致命的，在这一章完全无害** ——
//   因为题面把 p 的下界抬到了 10⁶。
//   > **同一句代码危不危险，取决于数据的取值范围**（第 33 章立的那条，这是第三次现场）。
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using i128 = __int128;

ll p;

/** 快速幂 —— 第 42 章那五行 */
ll power(ll a, ll b) {
    ll res = 1 % p;
    a %= p;
    if (a < 0) a += p;
    while (b) {
        if (b & 1) res = (i128)res * a % p;
        a = (i128)a * a % p;
        b >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    if (!(cin >> p >> q)) return 0;

    vector<pair<int, int>> qs(q);
    int maxn = 0;
    for (auto& [n, k] : qs) { cin >> n >> k; maxn = max(maxn, n); }

    vector<ll> fac(maxn + 1), inv(maxn + 1);
    fac[0] = 1;                                    // ⚠ 这一章 p > 10⁶，所以它是对的
    for (int i = 1; i <= maxn; i++) fac[i] = (i128)fac[i - 1] * i % p;

    inv[maxn] = power(fac[maxn], p - 2);           // ⚠ 是 p−2，不是 p−1
    for (int i = maxn; i >= 1; i--)                // ★ 从大往小倒推，只要一次快速幂
        inv[i - 1] = (i128)inv[i] * i % p;

    string out;
    int zeros = 0;
    for (auto& [n, k] : qs) {
        ll v;
        if (k > n) v = 0;                          // ⚠ k > n 时是 0
        else v = (ll)((i128)fac[n] * inv[k] % p * inv[n - k] % p);
        if (v == 0) zeros++;
        out += to_string(v);
        out += '\n';
    }
    out += to_string(zeros);                       // ★ 末行：答案是 0 的有几组
    out += '\n';

    cout << out;
    return 0;
}

// ✗ 错误版本：逆元用 `b^(p−1)` 而不是 `b^(p−2)`
//
//   费马小定理说的是 `b^(p−1) ≡ 1`，所以 `b^(p−1)` 算出来**恒等于 1** ——
//   于是所有的逆元阶乘都从 1 开始倒推，整张表全错。
//
// 靠什么现形：几乎什么数据都行 —— **整张逆元表都是从 1 开始倒推的**，全废。★ 它是这一章的基线。
// ⚠ 唯一蒙对的是 `n = k = 0` 那一组（`C(0,0) = 1`，正好和「全 1」的表撞上）。
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using i128 = __int128;

ll p;

/** 快速幂 —— 第 42 章那五行 */
ll power(ll a, ll b) {
    ll res = 1 % p;
    a %= p;
    if (a < 0) a += p;
    while (b) {
        if (b & 1) res = (i128)res * a % p;
        a = (i128)a * a % p;
        b >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    if (!(cin >> p >> q)) return 0;

    vector<pair<int, int>> qs(q);
    int maxn = 0;
    for (auto& [n, k] : qs) { cin >> n >> k; maxn = max(maxn, n); }

    vector<ll> fac(maxn + 1), inv(maxn + 1);
    fac[0] = 1 % p;
    for (int i = 1; i <= maxn; i++) fac[i] = (i128)fac[i - 1] * i % p;

    inv[maxn] = power(fac[maxn], p - 1);           // ✗ 差一个数：这算出来恒等于 1
    for (int i = maxn; i >= 1; i--)                // ★ 从大往小倒推，只要一次快速幂
        inv[i - 1] = (i128)inv[i] * i % p;

    string out;
    int zeros = 0;
    for (auto& [n, k] : qs) {
        ll v;
        if (k > n) v = 0;                          // ⚠ k > n 时是 0
        else v = (ll)((i128)fac[n] * inv[k] % p * inv[n - k] % p);
        if (v == 0) zeros++;
        out += to_string(v);
        out += '\n';
    }
    out += to_string(zeros);                       // ★ 末行：答案是 0 的有几组
    out += '\n';

    cout << out;
    return 0;
}

// ✗ 错误版本：逆元阶乘**从小往大推**（方向反了）
//
//   正确的是 `((i−1)!)⁻¹ = (i!)⁻¹ · i`（从大往小）。
//   反过来写成 `(i!)⁻¹ = ((i−1)!)⁻¹ · i` 就完全不对了 —— 那个 i 该乘的是**逆元的方向**。
//
// 靠什么现形：★ 要有 `k ∉ {0, n}` 的询问，而且 **n ≥ 2**（n ≤ 1 时那张表太短，看不出来）。
// ★ 和第 21 章那条「填表顺序由依赖方向决定」是同一件事的第 N 次：
//   **递推方向写反不报错、不崩溃，只是安静地给你错答案。**
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using i128 = __int128;

ll p;

/** 快速幂 —— 第 42 章那五行 */
ll power(ll a, ll b) {
    ll res = 1 % p;
    a %= p;
    if (a < 0) a += p;
    while (b) {
        if (b & 1) res = (i128)res * a % p;
        a = (i128)a * a % p;
        b >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    if (!(cin >> p >> q)) return 0;

    vector<pair<int, int>> qs(q);
    int maxn = 0;
    for (auto& [n, k] : qs) { cin >> n >> k; maxn = max(maxn, n); }

    vector<ll> fac(maxn + 1), inv(maxn + 1);
    fac[0] = 1 % p;
    for (int i = 1; i <= maxn; i++) fac[i] = (i128)fac[i - 1] * i % p;

    inv[0] = 1 % p;
    for (int i = 1; i <= maxn; i++)                // ✗ 方向反了：从小往大推
        inv[i] = (i128)inv[i - 1] * i % p;

    string out;
    int zeros = 0;
    for (auto& [n, k] : qs) {
        ll v;
        if (k > n) v = 0;                          // ⚠ k > n 时是 0
        else v = (ll)((i128)fac[n] * inv[k] % p * inv[n - k] % p);
        if (v == 0) zeros++;
        out += to_string(v);
        out += '\n';
    }
    out += to_string(zeros);                       // ★ 末行：答案是 0 的有几组
    out += '\n';

    cout << out;
    return 0;
}

// ✗ 错误版本：阶乘那一行**忘了取模**
//
//   `fac[i] = fac[i-1] * i` —— 不取模的话，`fac[21]` 就已经超过 long long 了。
//
// 靠什么现形：★ 只要 **n ≥ 21** 就必现（21! ≈ 5.1×10¹⁹ > 9.22×10¹⁸）。
//   ⚠ 而「顺手」写的生成器如果只造 `n ≤ 20` 的小数据，**它一轮都抓不到** ——
//   ★ 第 38、40、42 章那条：**先估一估多大的数据才溢出**，这一章的那条线是 **n = 21**。
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using i128 = __int128;

ll p;

/** 快速幂 —— 第 42 章那五行 */
ll power(ll a, ll b) {
    ll res = 1 % p;
    a %= p;
    if (a < 0) a += p;
    while (b) {
        if (b & 1) res = (i128)res * a % p;
        a = (i128)a * a % p;
        b >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    if (!(cin >> p >> q)) return 0;

    vector<pair<int, int>> qs(q);
    int maxn = 0;
    for (auto& [n, k] : qs) { cin >> n >> k; maxn = max(maxn, n); }

    vector<ll> fac(maxn + 1), inv(maxn + 1);
    fac[0] = 1 % p;
    for (int i = 1; i <= maxn; i++) fac[i] = fac[i - 1] * i;   // ✗ 忘了 % p

    inv[maxn] = power(fac[maxn], p - 2);           // ⚠ 是 p−2，不是 p−1
    for (int i = maxn; i >= 1; i--)                // ★ 从大往小倒推，只要一次快速幂
        inv[i - 1] = (i128)inv[i] * i % p;

    string out;
    int zeros = 0;
    for (auto& [n, k] : qs) {
        ll v;
        if (k > n) v = 0;                          // ⚠ k > n 时是 0
        else v = (ll)((i128)fac[n] * inv[k] % p * inv[n - k] % p);
        if (v == 0) zeros++;
        out += to_string(v);
        out += '\n';
    }
    out += to_string(zeros);                       // ★ 末行：答案是 0 的有几组
    out += '\n';

    cout << out;
    return 0;
}

// ✗ 错误版本：最后那一步**三个数连乘、中间不取模**（而且没有 `__int128`）
//
//   `fac[n] * inv[k] * inv[n-k] % p`：三个因子都在 `[0, p)` 里。
//   · p ≈ 10⁶ 时三个一乘是 10¹⁸ —— **勉强还在 long long 里，它居然是对的**；
//   · p ≈ 10⁹ 时就是 **10²⁷** —— 当场绕回去。
//
// 靠什么现形：★★ 要 **p 大过一条具体的线**：`p³ > 9.22×10¹⁸ ⇒ p > 2.1×10⁶`。
//   ⚠ 题面给的范围是 `10⁶ < p ≤ 10⁹`，也就是说**这条线就在题面范围的最下面一点点** ——
//   顺手挑一个「一百万零三」当模数，它就安全落地了。
//   ★ 第 42 章那条（溢出线要算到小数点后两位）的第二次现场，而这一次那条线**离下界只差一倍**。
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using i128 = __int128;

ll p;

/** 快速幂 —— 第 42 章那五行 */
ll power(ll a, ll b) {
    ll res = 1 % p;
    a %= p;
    if (a < 0) a += p;
    while (b) {
        if (b & 1) res = (i128)res * a % p;
        a = (i128)a * a % p;
        b >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    if (!(cin >> p >> q)) return 0;

    vector<pair<int, int>> qs(q);
    int maxn = 0;
    for (auto& [n, k] : qs) { cin >> n >> k; maxn = max(maxn, n); }

    vector<ll> fac(maxn + 1), inv(maxn + 1);
    fac[0] = 1 % p;
    for (int i = 1; i <= maxn; i++) fac[i] = (i128)fac[i - 1] * i % p;

    inv[maxn] = power(fac[maxn], p - 2);           // ⚠ 是 p−2，不是 p−1
    for (int i = maxn; i >= 1; i--)                // ★ 从大往小倒推，只要一次快速幂
        inv[i - 1] = (i128)inv[i] * i % p;

    string out;
    int zeros = 0;
    for (auto& [n, k] : qs) {
        ll v;
        if (k > n) v = 0;                          // ⚠ k > n 时是 0
        else v = fac[n] * inv[k] * inv[n - k] % p;   // ✗ 三个连乘、中间不取模、也没 __int128
        if (v == 0) zeros++;
        out += to_string(v);
        out += '\n';
    }
    out += to_string(zeros);                       // ★ 末行：答案是 0 的有几组
    out += '\n';

    cout << out;
    return 0;
}

// ✗ 错误版本：**k > n 时没返回 0**（直接套公式）
//
//   `n − k` 变成负数，`inv[n-k]` 就是越界访问 —— 跑出来是内存里的垃圾（或者直接崩）。
//
// 靠什么现形：★★ 询问里必须出现 **k > n**。
//   ⚠ 而「顺手」写的生成器多半是 `n = rnd(...); k = rnd(0, n);` ——
//   **它永远造不出 k > n**。★ 第 27~42 章那条「顺手写法」的第十四次：
//   这次加的性质是「**k 一定不超过 n**」，而题面明明写着 `0 ≤ n, k ≤ 10⁶`（两个各自独立）。
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using i128 = __int128;

ll p;

/** 快速幂 —— 第 42 章那五行 */
ll power(ll a, ll b) {
    ll res = 1 % p;
    a %= p;
    if (a < 0) a += p;
    while (b) {
        if (b & 1) res = (i128)res * a % p;
        a = (i128)a * a % p;
        b >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    if (!(cin >> p >> q)) return 0;

    vector<pair<int, int>> qs(q);
    int maxn = 0;
    for (auto& [n, k] : qs) { cin >> n >> k; maxn = max(maxn, n); }

    vector<ll> fac(maxn + 1), inv(maxn + 1);
    fac[0] = 1 % p;
    for (int i = 1; i <= maxn; i++) fac[i] = (i128)fac[i - 1] * i % p;

    inv[maxn] = power(fac[maxn], p - 2);           // ⚠ 是 p−2，不是 p−1
    for (int i = maxn; i >= 1; i--)                // ★ 从大往小倒推，只要一次快速幂
        inv[i - 1] = (i128)inv[i] * i % p;

    string out;
    int zeros = 0;
    for (auto& [n, k] : qs) {
        ll v;
        v = (ll)((i128)fac[n] * inv[k] % p * inv[n - k] % p);
        if (v == 0) zeros++;
        out += to_string(v);
        out += '\n';
    }
    out += to_string(zeros);                       // ★ 末行：答案是 0 的有几组
    out += '\n';

    cout << out;
    return 0;
}

// ✗ 错误版本：逆元阶乘倒推**少走了最后一步**（循环写成 `i >= 2`）
//
//   于是 `inv[0]` 从来没被算出来，一直是 0 —— 而 `inv[0]` 正是
//   `C(n, 0)` 和 `C(n, n)` 要用的那一个。
//
// 靠什么现形：★★ 询问里必须出现 **k = 0 或 k = n**（那两种「取全部 / 一个都不取」的情况）。
//   ⚠ 而「顺手」写的生成器多半是 `k = rnd(1, n-1)`（觉得 0 和 n「太平凡了」）——
//   ★ 那正好把这个 bug 关在门外。这是「顺手写法」的第十五次。
// ⚠ 和 wrongFermat 正好是一对：那个**只在 k ∉ {0,n} 时错**，这个**只在 k ∈ {0,n} 时错**。
//   ⇒ **两端都得造**（第 31、38 章那条）。
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using i128 = __int128;

ll p;

/** 快速幂 —— 第 42 章那五行 */
ll power(ll a, ll b) {
    ll res = 1 % p;
    a %= p;
    if (a < 0) a += p;
    while (b) {
        if (b & 1) res = (i128)res * a % p;
        a = (i128)a * a % p;
        b >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    if (!(cin >> p >> q)) return 0;

    vector<pair<int, int>> qs(q);
    int maxn = 0;
    for (auto& [n, k] : qs) { cin >> n >> k; maxn = max(maxn, n); }

    vector<ll> fac(maxn + 1), inv(maxn + 1);
    fac[0] = 1 % p;
    for (int i = 1; i <= maxn; i++) fac[i] = (i128)fac[i - 1] * i % p;

    inv[maxn] = power(fac[maxn], p - 2);           // ⚠ 是 p−2，不是 p−1
    for (int i = maxn; i >= 2; i--)                // ✗ 少走一步：inv[0] 永远是 0
        inv[i - 1] = (i128)inv[i] * i % p;

    string out;
    int zeros = 0;
    for (auto& [n, k] : qs) {
        ll v;
        if (k > n) v = 0;                          // ⚠ k > n 时是 0
        else v = (ll)((i128)fac[n] * inv[k] % p * inv[n - k] % p);
        if (v == 0) zeros++;
        out += to_string(v);
        out += '\n';
    }
    out += to_string(zeros);                       // ★ 末行：答案是 0 的有几组
    out += '\n';

    cout << out;
    return 0;
}

// 正解 —— 阶乘 + 乘法逆元：**C(n,k) = n! · (k!)⁻¹ · ((n−k)!)⁻¹ (mod p)**
//
// ============ ★ 关键一步：除法在模意义下怎么做 ============
//
//   `C(n,k) = n! / (k! · (n−k)!)`。可**取模之下不能直接除** ——
//   `(a / b) mod p` 和 `(a mod p) / (b mod p)` 根本不是一回事。
//
//   ★ 办法是把「除以 b」换成「乘以 b 的**逆元**」：
//     **b⁻¹ 是那个满足 `b · b⁻¹ ≡ 1 (mod p)` 的数。**
//
//   而这个逆元存在的**充要条件**是 `gcd(b, p) = 1`（第 40 章的裴蜀定理：
//   `b·x + p·y = 1` 有整数解 ⟺ `gcd(b,p) | 1`）。
//   ⇒ **p 是质数**的时候，只要 b 不是 p 的倍数就一定有逆元。
//
//   怎么求？**费马小定理**（第 42 章 verify.cpp 验过的那条）：
//     p 是质数、b 不是 p 的倍数 ⇒ `b^(p−1) ≡ 1` ⇒ **`b⁻¹ ≡ b^(p−2)`**。
//   ⚠ 是 **p−2**，不是 p−1 —— 差一个数，答案就恒等于 1。
//   于是逆元 = 一次快速幂（第 42 章那五行原样搬过来）。
//
// ============ ★ 这一章串起了前面三章 ============
//
//   · 第 40 章：逆元存在 ⟺ gcd = 1（裴蜀定理）；
//   · 第 41 章：p 得是**质数**，费马小定理才成立；
//   · 第 42 章：算 `b^(p−2)` 靠**快速幂**。
//   ⇒ 数学这一块四章，到这里正好收口。
//
// ⚠⚠ 而这套办法有一个必须写明的前提：**p 必须大于 n**。
//   否则 `n!` 里含有 p 这个因子 ⇒ `n! ≡ 0`，而 0 没有逆元，整套公式当场失效
//   （smallP.cpp 把这件事跑出来给你看，正解是 Lucas 定理 —— 这一章只点到为止）。
//   所以题面写的是 `10⁶ < p ≤ 10⁹` 而 `n ≤ 10⁶`。
//
// ============ ★ 逆元阶乘的那个倒推，值得单独看一眼 ============
//
//   一个个求 `(i!)⁻¹` 要 n 次快速幂（O(n log p)）。其实只要**一次**：
//     先求 `(n!)⁻¹`，然后 **`((i−1)!)⁻¹ = (i!)⁻¹ · i`** —— 从大往小倒着推。
//   （因为 `(i−1)! = i! / i`，取逆元就是乘 i。）
//   ⇒ 预处理 O(n + log p)，每次询问 O(1)。
//
// 复杂度 O(n + log p + q)。

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using i128 = __int128;

ll p;

/** 快速幂 —— 第 42 章那五行 */
ll power(ll a, ll b) {
    ll res = 1 % p;
    a %= p;
    if (a < 0) a += p;
    while (b) {
        if (b & 1) res = (i128)res * a % p;
        a = (i128)a * a % p;
        b >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    if (!(cin >> p >> q)) return 0;

    vector<pair<int, int>> qs(q);
    int maxn = 0;
    for (auto& [n, k] : qs) { cin >> n >> k; maxn = max(maxn, n); }

    vector<ll> fac(maxn + 1), inv(maxn + 1);
    fac[0] = 1 % p;
    for (int i = 1; i <= maxn; i++) fac[i] = (i128)fac[i - 1] * i % p;

    inv[maxn] = power(fac[maxn], p - 2);           // ⚠ 是 p−2，不是 p−1
    for (int i = maxn; i >= 1; i--)                // ★ 从大往小倒推，只要一次快速幂
        inv[i - 1] = (i128)inv[i] * i % p;

    string out;
    int zeros = 0;
    for (auto& [n, k] : qs) {
        ll v;
        if (k > n) v = 0;                          // ⚠ k > n 时是 0
        else v = (ll)((i128)fac[n] * inv[k] % p * inv[n - k] % p);
        if (v == 0) zeros++;
        out += to_string(v);
        out += '\n';
    }
    out += to_string(zeros);                       // ★ 末行：答案是 0 的有几组
    out += '\n';

    cout << out;
    return 0;
}