题目：https://www.lydsy.com/JudgeOnline/problem.php?id=4403
先说说自己的想法吧。
设f[ i ][ j ]表示当前在倒数第 i 个位置，当前和后面的最高的列(最大的数)是 j 的方案数。
考虑当前填0，则用f[ i-1][ j ]转移；当前填1，相当于把后面的都消去最底下一行，用f[ i-1 ][ j-1 ]转移。
所以f[ i ][ j ]=∑(k:0~j)f[ i-1 ][ k ]。然后矩阵优化。
结果发现 j 的范围达到1e9，也就是要建1e9*1e9的矩阵。于是萎了。
看TJ：https://blog.csdn.net/Clove_unique/article/details/68491395
关键的思路可能在于发现随便选即可，之后排序。
没错，不用 +i 转换成升序也是可以这样转化的。很经典。
C( )里必须判断 if(n<m)return 0; ！因为n%mod,m%mod时很容易传进n<m的参数！
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
const int mod=1e6+;
int T,n,m,l,r,jc[mod+],jcn[mod+];
int pw(int x,int k)
{
int ret=;while(k){if(k&)ret=(ll)ret*x%mod;x=(ll)x*x%mod;k>>=;}return ret;
}
void init()
{
jc[]=;
for(int i=;i<mod;i++)jc[i]=(ll)jc[i-]*i%mod;
jcn[mod-]=pw(jc[mod-],mod-);
for(int i=mod-;i>=;i--)jcn[i]=(ll)jcn[i+]*(i+)%mod;
}
int C(int n,int m)
{
if(n<m)return ;//////
return (ll)jc[n]*jcn[m]%mod*jcn[n-m]%mod;
}
int lucas(int n,int m)
{
if(!m)return ;if(n<mod&&m<mod)return C(n,m);
return (ll)lucas(n/mod,m/mod)*C(n%mod,m%mod)%mod;
}
int main()
{
init();
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&l,&r);m=r-l+;
printf("%d\n",(lucas(n+m,m)-+mod)%mod);
}
return ;
}