思路与算法

目标是 $S(n,k)=\sum_{i=0}^k\binom ni\bmod p$，$p=2333$。先对各项取模再对总和取模，与直接求此余数相同。约定 $i>n$ 时组合数为0，因此 $k\ge n$ 时答案是全行和 $2^n\bmod p$。

2333是素数。将 $n,k,i$ 写成 $p$ 进制，分别记各位为 $a_j,b_j,c_j$。Lucas定理给出 $\binom ni\equiv\prod_j\binom{a_j}{c_j}$。对所有 $i\le k$ 求和，可以从高位到低位，按照“第一次小于 $k$ 的位置”分类，而不枚举 $i$。

预处理小行前缀

$$H[a][b]=\sum_{t=0}^b\binom at\bmod p,\quad 0\le a,b<p,$$

并令 $H[a][-1]=0$。使用Pascal滚动行计算每行系数，再累加前缀。小组合数可由相邻前缀的差取得，行中超过 $a$ 的项为0。

处理位置 $h$ 时，设更高位全部等于 $k$ 的系数乘积为 $Q=\prod_{j>h}\binom{a_j}{b_j}$。当前位若取小于 $b_h$ 的任意值，则低位可自由选取，其贡献为

$$Q\,H[a_h][b_h-1]\,2^{\sum_{j<h}a_j}\pmod p.$$

这里每个自由低位的系数和由二项式定理为 $\sum_t\binom{a_j}t=2^{a_j}$。累加这类贡献后，若 $b_h>a_h$，等号分支系数为0，立即结束；否则把 $Q$ 乘 $\binom{a_h}{b_h}$，继续下一位。全部位都相等且合法时，最后再加上 $Q$，对应 $i=k$。

预存 $2^e\bmod p$，$0\le e<p-1$，用费马周期把指数减为模 $p-1$；自由低位只需维护数字和，不构造巨大的实际低位数。每组最多6位，配合缓冲读写处理百万组输入。

正确性说明

Lucas将每个下标 $i$ 的系数精确分解成数位系数乘积。任意 $i<k$ 都有唯一的最高不同位 $h$：更高位与 $k$ 相等，当前位小于 $k$，更低位任意。因此上述分类不重不漏。

固定 $h$ 后，高位贡献为 $Q$，当前位贡献的总和是 $H[a_h][b_h-1]$，各低位可以独立选择，所以低位乘积的总和等于各位行和的乘积，恰为 $2^{\sum_{j<h}a_j}$。若某一等号位超出对应 $n$ 位，其小组合数为0，所有继续相等的贡献均为0，可以终止；此前较小位分支已经统计完整。若所有位都可继续，则唯一未计的是 $i=k$，补入最终系数乘积。故所有 $i\le k$ 的模系数之和被正确计算，超过 $n$ 的非法数位系数自动为0。

Pascal递推与前缀差保证预处理值正确；$2$ 与素数 $p$ 互质，所以按 $p-1$ 约简指数保持余数。$k\ge n$ 的全行和特判同样由二项式定理成立，包括 $n=0$ 时唯一系数1。故程序输出目标总威力的余数。

复杂度

令 $d$ 为参数的 $p$ 进制位数，本范围 $d\le6$。表分配、初始化、Pascal和全部行前缀预处理为 $O(p^2)$，2幂表为 $O(p)$。每组按位计算 $O(d)$，若全部输入字节数为 $B$，含读写和初始化总时间为 $O(p^2+Td+B)$。额外空间 $O(p^2+p+d)$，前缀值小于2333，使用16位无符号数组，占 $2p^2$ 字节，约10.4MiB；读写缓冲为固定大小，不保存全部查询。

易错点

1. 需要的是前缀和，不能只对 $\binom nk$ 使用一次Lucas，也不能逐项循环到巨大 $k$。
2. 对当前位“小于”的分支先累加，再判断能否沿“相等”继续；$b_h>a_h$ 时已经有合法较小分支。
3. 自由后缀按每位独立系数和计算，权重为2的低位数字和次方；不要把未经约简的巨大指数塞入32位。
4. 2幂周期用 $p-1$，不是 $p$。小组合数由前缀相减后要规范化负余数。
5. 覆盖 $k=0$、$k\ge n$、进制进位、数位超界、最大 $n$ 和百万组联合大规模。所有中间模乘分步约简，单次乘积小于 $2333^2$，32位安全；原参数使用64位。
6. 百万组测试中 $n$ 的低5位均为 $p-1$，但每个 $k$ 不同且参考程序实际走完整6位。由 $\binom{p-1}j\equiv(-1)^j$ 可独立得出短输出，并与递归分块程序逐行核对；这没有降低查询规模或修改资源限制。另有20份原公开点全部域与独立答案核验，最终取5点并补4个边界和样例。训练数据非官方原版。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
const int P = 2333;
struct Input {
    char data[65536];
    int at = 0, len = 0;
    int get() {
        if (at == len) {
            len = fread(data, 1, sizeof data, stdin);
            at = 0;
            if (!len)
                return EOF;
        }
        return data[at++];
    }
    ull next() {
        int c = get();
        while (c <= 32 && c != EOF)
            c = get();
        ull v = 0;
        while (c >= '0' && c <= '9') {
            v = v * 10 + c - '0';
            c = get();
        }
        return v;
    }
};
struct Output {
    char data[1 << 20];
    int at = 0;
    void flush() {
        fwrite(data, 1, at, stdout);
        at = 0;
    }
    void number(int v) {
        if (at + 8 >= int(sizeof data))
            flush();
        char digits[5];
        int count = 0;
        do {
            digits[count++] = char('0' + v % 10);
            v /= 10;
        } while (v);
        while (count)
            data[at++] = digits[--count];
        data[at++] = '\n';
    }
    ~Output() {
        flush();
    }
};
int main() {
    vector<unsigned short> pref(P * P);
    vector<int> row(P), two(P - 1);
    row[0] = 1;
    two[0] = 1;
    for (int i = 1; i < P - 1; i++)
        two[i] = two[i - 1] * 2 % P;
    for (int n = 0; n < P; n++) {
        row[n] = 1;
        for (int j = n - 1; j > 0; j--) {
            row[j] += row[j - 1];
            if (row[j] >= P)
                row[j] -= P;
        }
        int sum = 0;
        for (int j = 0; j < P; j++) {
            sum += row[j];
            if (sum >= P)
                sum -= P;
            pref[n * P + j] = sum;
        }
    }
    Input in;
    Output out;
    int tests = in.next();
    while (tests--) {
        ull n = in.next(), k = in.next();
        if (k >= n) {
            out.number(two[n % (P - 1)]);
            continue;
        }
        int a[8]{}, b[8]{}, size = 0, sum = 0;
        while (n || k) {
            a[size] = n % P;
            b[size] = k % P;
            sum += a[size];
            size++;
            n /= P;
            k /= P;
        }
        int prefix = 1, answer = 0;
        bool equal = true;
        for (int pos = size - 1; pos >= 0; pos--) {
            sum -= a[pos];
            int offset = a[pos] * P;
            if (b[pos]) {
                int add = prefix * pref[offset + b[pos] - 1] % P * two[sum % (P - 1)] % P;
                answer += add;
                if (answer >= P)
                    answer -= P;
            }
            if (b[pos] > a[pos]) {
                equal = false;
                break;
            }
            int choose = pref[offset + b[pos]] - (b[pos] ? pref[offset + b[pos] - 1] : 0);
            if (choose < 0)
                choose += P;
            prefix = prefix * choose % P;
        }
        if (equal) {
            answer += prefix;
            if (answer >= P)
                answer -= P;
        }
        out.number(answer);
    }
}