思路与算法

令 $M=R-L+1$ 为可用值种数。单调不降序列完全由每种值出现的次数 $c_1,\ldots,c_M$ 决定，这些次数均非负，总和是序列长度。为了把“长度至多 $N$”改成等式，引入松弛量 $s=N-\sum c_i\ge0$，得到 $M+1$ 个非负变量之和为 $N$。

插板法给出 $\binom{N+M}{M}$ 个频数与松弛量向量；其中全频数为0对应空序列，必须减去1。因此答案为 $\binom{N+M}{M}-1$ 模1000003。

Lucas定理把大组合数拆成素数 $P$ 进制的数位乘积：

先预处理 $0,\ldots,P-1$ 的阶乘和逆阶乘。每一位都小于 $P$，对应阶乘非零，若 $m_j>n_j$ 就返回0，否则乘上该位的小组合数。然后两参数整除 $P$，直到都为0。这里 $P=1000003$，$N+M\le2\times10^9$。用64位计算宽度及参数和，按Lucas得到组合数余数后规范化减1。

正确性说明

给定一个合法非空单调不降序列，统计各值出现次数，再补上唯一松弛量，得到和为 $N$ 的非负整数向量。反过来，从任意这样的向量按值从小到大重复输出相应次数，得到唯一长度不超过 $N$ 的单调不降序列。两者一一对应，唯一的空序列对应全部频数为0，所以插板总数恰减1。

大组合数在素模下由Lucas拆成数位乘积，各位小阶乘可逆，故求得组合数余数。最后的加模再减1与整数计数减去空序列同余，得到所求结果。

复杂度

令 $P=1000003$。初始化与阶乘、逆阶乘预处理 $O(P)$，模逆快速幂 $O(\log P)$。单组查询为 $O(\log_P(N+M+1))$ 位，含全部输入总时间 $O(P+\log P+T+\sum_q\log_P(N_q+M_q+1))$。额外空间 $O(P)$，没有按区间长度或 $N$ 建表。

易错点

1. 单调不降允许相等，不能按严格递增子集计数；只有区间宽度影响计数，端点平移不改变答案。
2. 空序列不在长度1至 $N$ 中，组合数总数要减1。
3. Lucas余数为0时，减1的规范化结果是 $P-1$，不是负数；真实非空方案数的余数也可能为0。
4. $L=R$ 时每种长度恰有一种序列，答案为 $N\bmod P$；$N=1$ 时答案为 $M\bmod P$。
5. 覆盖最大参数、数位进位与最多100组输入。候选含N=0或L=0的整组测试文件不满足当前源域，已排除且未修改原包。独立答案用p进阶乘单位方法及小范围完整多重集合枚举验证。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int P = 1000003;
ll power(ll a, ll e) {
    ll result = 1;
    while (e) {
        if (e & 1)
            result = result * a % P;
        a = a * a % P;
        e >>= 1;
    }
    return result;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<ll> fact(P), inv(P);
    fact[0] = 1;
    for (int i = 1; i < P; i++)
        fact[i] = fact[i - 1] * i % P;
    inv[P - 1] = power(fact[P - 1], P - 2);
    for (int i = P - 1; i; i--)
        inv[i - 1] = inv[i] * i % P;
    auto lucas = [&](ll n, ll m) -> ll {
        ll answer = 1;
        while (n || m) {
            int a = n % P, b = m % P;
            if (b > a)
                return 0;
            answer = answer * fact[a] % P * inv[b] % P * inv[a - b] % P;
            n /= P;
            m /= P;
        }
        return answer;
    };
    int tests;
    cin >> tests;
    while (tests--) {
        ll n, l, r;
        cin >> n >> l >> r;
        ll width = r - l + 1;
        cout << (lucas(n + width, width) - 1 + P) % P << '\n';
    }
}