1550D - Excellent Arrays - CodeForces Solution

#include <bits/stdc++.h>
#define ll long long
#define db long double
#define N 200005
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define fst first
#define snd second
using namespace std;
ll n,i,j,l,r,gt[N],ng[N],res,test;
const ll mod=round(1e9)+7;
ll lt(ll a,ll b)
{
    if(b==0) return 1;
    ll tg=lt(a,b/2);
    return (b%2==0) ? tg*tg%mod : tg*tg%mod*a%mod;
}
ll C(int k,int n)
{
    return (k<0 || k>n) ? 0 : gt[n]*ng[k]%mod*ng[n-k]%mod;
}
void solve()
{
    cin>>n>>l>>r;
    gt[0]=1;
    for(i=1;i<=n;i++) gt[i]=gt[i-1]*i%mod;
    ng[n]=lt(gt[n],mod-2);
    for(i=n-1;i>=0;i--) ng[i]=ng[i+1]*(i+1)%mod;
    res=0;
    for(i=1;i<=n;i++)
    {
        j=max(r-i+l,1LL);
        ll sum=0;
        if(j<=i)
        {
            sum=C(n/2-n+i,i-j);
            if(n&1) sum=(sum+C(n/2+1-n+i,i-j))%mod;
        }
        else if(j==i+1 && (n-i==n/2 || n-i==(n+1)/2))
            sum=1;
        res=(res+sum*(r-i))%mod;
    }
 
    for(i=1;i<=n;i++)
    {
        j=min(r-i+l-1,n);
        ll sum=0;
        if(j>=i)
        {
            sum=C(n/2-i+1,j-i);
            if(n&1) sum=(sum+C(n/2+1-i+1,j-i))%mod;
        }
        else if(j==i-1 && (i-1==n/2 || i-1==(n+1)/2))
            sum=1;
        res=(res+sum*(i-l))%mod;
    }
    cout<<res<<'\n';
}
int main()
{
 //   freopen("ntu.inp","r",stdin);
   // freopen("ntu.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>test;
    while(test--) solve();
}