假设存在一个满足条件的长度为i的不下降序列（显然是一定存在的）那么只需要从中选出i个数即可
（不必在意选出具体数的大小，可以把满足条件的序列写下来，选几个数感受一下）。
但是$n \choose m $里的 \(m\) 的是就是 \((r-l+1)\) 吗?
乍一看是这样的，但是这样会出现一个问题，单调不下降子序列中的数可以重复，但如果只是从\(l\)到\(r\)去选数，那将会使结果变小。
所以可以先找出（当然是在脑子里找出）满足条件的长度为\(i\)的序列，然后和\(l\)到\(r\)这几个数合起来，从这几个数里面选出\(i\)个数。即 \(r-l+1+i\choose r-l+1\)
然后就从1$ \rightarrow $n枚举长度再求和即可
所以答案为
\[\sum ^n _{i=1} {\ r \ - \ l\ + \ 1 \ + \ i \choose \ i } \]但是此时O(\(n^+\))的时间复杂度一定是不可行的，而\(i\)的值又一直发生改变，无法化简。
所以我们可以把 \(r-l+1+i \choose i\) 写为\(r-l+1+i \choose r-l+1\)，再设\(x=r-l+1\)那么原式变为
\[\sum ^n _{i=1} {x+i\choose \ i } \]也就是 $\qquad $ \({x+1 \choose x}\)+\({x+2 \choose x}\)+\({x+3 \choose x}\)+……+\({x+n \choose x}\)
接下来就是化简……
首先看一下\(n \choose m\) +\(n \choose m+1\)的结果是什么
\[{n\choose m}+{n\choose m+1} \]\[={\frac{n!}{m!*(n-m)!}} + { \frac {n!} {(m+1)!*(n-m-1)!}} \]\[={\frac{n!*(m+1)}{(m+1)!*(n-m!)}}+{\frac{n!*(n-m)}{(m+1)!*(n-m)!}} \]\[={\frac{(m+1+n-m)*n!}{(m+1)!*(n-m)!} } \]\[={\frac{(n+1)!}{(m+1)!*(n-m)!}} \]\[= {n+1 \choose m+1} \]所以有$${n\choose m}+{n\choose m+1}={n+1 \choose m+1}$$
那么给答案前面加一个\(x+1 \choose x+1\)，根据刚刚的公式，\(x+1 \choose x+1\) + \(x+1 \choose x\) = \(x+2 \choose x+1\)
$\quad $$\quad $$\quad $$\quad $ 而\(x+2 \choose x\) + \(x+2 \choose x+1\) = \(x+3 \choose x+1\)
以此类推，最终答案是\({x+n\choose n}-1\)
附上代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define what_can_I_say main
#define crash_on_you 0
const int N=1e9+100,p=1000003;
int i,j,n,m,ans,t,l,r,x,fact[p+100],ny[p+100];
int op(int a,int b){
int ans=1;
while(b){
if(b&1)ans=ans*a%p;
a=a*a%p;
b>>=1;
}
return ans;
}
int c(int n,int m){
if(n<m)return 0;
return 1ll*(1ll*fact[n]*op(fact[m],p-2)%p)*op(fact[n-m],p-2)%p;
}
int lucas(int n,int m){
if(n<=p&&m<=p)return c(n,m);
return c(n%p,m%p)*lucas(n/p,m/p);
}
signed what_can_I_say(){
fact[0]=1;
for(i=1;i<p;i++)fact[i]=fact[i-1]*i%p;
scanf("%lld",&t);
while(t--){
scanf("%lld%lld%lld",&n,&l,&r);
x=r-l+1;
printf("%lld\n",(lucas(x+n,n)-1+p)%p);
}
return crash_on_you;
}