分析

这里可以枚举序列的长度，假设当前的序列长度为k，则存在两种分析方式（第二种方式更加简单）：

分析方式1

• 使用这种方式分析的目的是为了介绍不等式使用隔板法求解的过程。

• 对于[L, R]这个区间中满足条件的数据，我们可以将区间变为[0, R-L]满足条件的数据，两者是一一对应的，因此，我们只需要考虑在区间[0, R-L]合法的序列即可，假设合法的序列为：

$$ 0 \le a_1 \le a_2 \le … \le a_k \le R-L $$

我们构造a的差分数组b，即：
$$ b_1 = a_1 \\\\ b_2 = a_2 - a_1 \\\\ … \\\\ b_k = a_k - a_{k-1} $$
则问题就变成了：对于任意$b_i \ge 0$，满足 $b_1 + b_2 + … + b_k \le R-L$ 的方案数。

• 如何求解这个不等式的方案数呢？直接求不是很好求，我们还需要一步等价转换，令 $c_i = b_i + 1$，则问题可以转换为：对于任意的$c_i > 0$，满足$c_1 + c_2 + … + c_k \le R-L+k$，此时就可以使用隔板法分析求解。

• 相当于一共R-L+k个小球排成一排，除了第一个小球前面不能放置隔板，其余的R-L+k个位置（包括最后一个小球的后面）都可以放置隔板，需要放置k个隔板，最后一个隔板后的小球不算入，前面的k-1个隔板会得到k份，每一份对应一个$c_i$，如下图：

• 因此，因此对于当前k来说答案就是：

$$ C_{R-L+k}^k $$

分析方式2

• 我们要求出满足 $L \le a_1 \le a_2 \le … \le a_k \le R$ 的方案数，我们可以构造$b_i = a_i + i - 1$，则问题可以转化为：

$$ L \le b_1 < b_2 < … < b_k \le R + k - 1 $$

的方案数，这就很简单了，相当于在区间[L, R+k-1]中选取k个元素的方案数，该区间一共R-L+k个数，因此对于当前k来说答案就是：
$$ C_{R-L+k}^k $$

• 上述两种分析方法已经结束，之后的分析是从 $C_{R-L+k}^k$ 开始分析。

• 因为序列的长度n最大为$10^9$，十亿项加和不可取，我们考虑对结果进行化简，最终的答案为（令$m = R - L$）：

$$ \sum_{k=1}^n C_{m+k}^k = C_{m+1}^1 + C_{m+2}^2 + … + C_{m+n}^n \\\\ = C_{m+1}^m + C_{m+2}^m + … + C_{m+n}^m $$

对上述式子加上一项$C_{m+1}^{m+1}$，再减去一项$C_{m+1}^{m+1}$，并根据公式：$C_a^b = C_{a-1}^{b-1} + C_{a-1}^{b}$，可知：
$$ C_{m+1}^m + C_{m+2}^m + … + C_{m+n}^m \\\\ = (C_{m+1}^{m+1} + C_{m+1}^m) + C_{m+2}^m + … + C_{m+n}^m - C_{m+1}^{m+1} \\\\ = C_{m+2}^{m+1} + C_{m+2}^m + … + C_{m+n}^m - C_{m+1}^{m+1} \\\\ = ............ \\\\ = C_{m+n+1}^{m+1} - 1 $$

• 因此本题最终的答案是：

$$ C_{R-L+n+1}^{R-L+1} - 1 $$

• 我们发现R、L、k的范围都很大，求这个组合数需要使用AcWing 887. 求组合数 III中的方法，即使用卢卡斯定理，详细内容请参考：网址。

• 卢卡斯定理（要求式中a、b为非负整数，p为质数）：

$$ C_a^b = C_{a \ (mod \ p)} ^ {b \ (mod \ p)} \times C_{a / p} ^ {b / p} \ \ (mod \ p) $$

递归求解即可。

• 本题中$p=10^6+3$，可以验证是一个质数，可以使用lucas定理求解。

代码

#include <iostream>

using namespace std;

typedef long long LL;

const int mod = 1000003;  // 是一个质数，可以使用快速幂求逆元

int qmi(int a, int k) {

    int res = 1 % mod;
    while (k) {
        if (k & 1) res = (LL)res * a % mod;
        a = (LL)a * a % mod;
        k >>= 1;
    }
    return res;
}

// 根据定义计算C(a, b) % mod
int C(int a, int b) {

    if (a < b) return 0;

    int down = 1, up = 1;  // down: 分母, up: 分子
    for (int i = a, j = 1; j <= b; i--, j++) {
        up = (LL)up * i % mod;
        down = (LL)down * j % mod;
    }
    return (LL)up * qmi(down, mod - 2) % mod;
}

int Lucas(int a, int b) {
    if (a < mod && b < mod) return C(a, b);
    return (LL)C(a % mod, b % mod) * Lucas(a / mod, b / mod) % mod;
}

int main() {

    int T;
    cin >> T;
    while (T--) {
        int n, l, r;
        cin >> n >> l >> r;
        cout << (Lucas(r - l + n + 1, r - l + 1) - 1 + mod) % mod << endl;
    }

    return 0;
}