Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
5.4 kB
1
Indexable
Never
#include<bits/stdc++.h>
using namespace std;
#define all(v) ((v).begin()),((v).end())
#define sz(v) (v.size())
#define yes cout<<"Yes"<<'\n';
#define no cout<<"No"<<'\n';
#define endl '\n';
#define f(i,j,k) for(long long i=j;i<k;i++)
#define fb(i,j,k) for(long long i=j;i>=k;i--)
#define fs(i,j,k,p) for(long long i=j;i<k;i+=p)
#define fbs(i,j,k,p) for(long long i=j;i>=k;i-=p)
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define ff first
#define ss second
#define pi 3.141592653589793238462
typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<vector<int>> vvi;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pp ;
typedef vector<ll> vll;
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;}
ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);}
long long pow(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}
ll mod =1e9+7;

void add_divs(ll x, map<ll, ll>&divs){
    ll i = 2;
    while(i * i <= x){
        while (x % i == 0){
            divs[i]++;
            x /= i;
        }
        i++;
    }
    if(x > 1) divs[x]++;
}




ll n1;

ll mrg (ll x ,ll y )
{
    return (x+y)%mod;
}

struct segment_tree
{
    vector<ll> tree;
    void clear()
    {
        tree.clear();
    }

    void init(int num, const vector<ll>& a)
    {
        n1 = num;
        tree.assign(4 * n1, 0ll);
        build(a);
    }

    void build(const vector<ll>& a, int id=0,int ns = 0, int ne = n1-1)
    {
        if(ns==ne){
            tree[id] = a[ns];
            return ;
        }
        int l = 2*id+1;
        int r = l+1;
        int md = ns+(ne-ns)/2;
        build(a,l, ns, md);
        build(a,r, md+1, ne);
        tree[id] = mrg(tree[l],tree[r]);
    }


    ll query(int qs, int qe, int id=0, int ns=0, int ne=n1-1)
    {
        if(ns>qe || qs>ne){
            return 0; ///infnity
        }
        if(qs<=ns && qe>=ne){
            return tree[id];
        }
        int l = 2*id+1;
        int r = l+1;
        int md = ns+(ne-ns)/2;
        ll ndl = query(qs, qe, l, ns, md);
        ll ndr = query(qs, qe,r, md+1,ne);
        return mrg(ndl,ndr );
    }

    void upd(int pos , int val , int id=0, int ns=0,int ne=n1-1)
    {
        if(ns>pos || pos>ne){
            return;
        }
        if(ns==ne){
            tree[id]=val;
            return ;
        }
        int l = 2*id+1;
        int r = l+1;
        int md = ns+(ne-ns)/2;
        upd(pos, val,l, ns, md);
        upd(pos, val, r, md+1, ne);
        tree[id] = mrg(tree[l],tree[r]);
    }
} st ;
auto bin(long long n,vector<int> &v)
{
    long long i;
    v.push_back(0);
    for (i = 1 << 30; i > 0; i = i / 2)
    {
        if((n & i) != 0)
        {
            v.push_back(1);
        }
        else
        {
            v.push_back(0);
        }
    }
    return v;
}

vector<bool> premier(int x)
{
    vector<bool> pre(x+1,0);
    for(int i=2;i<x+1;i++)
    {
        if(!pre[i])
        {
            for(int j=2*i;j<=x;j+=i)
            {
                pre[j]=1;
            }
        }
    }
    return pre;
}
ll mult(ll a,ll b,ll n)
{
    return((a%n)*(b%n))%n;
}
ll sum(ll a,ll b,ll n)
{
    return((a%n)+(b%n))%n;
}
ll sub(ll a,ll b,ll n)
{
    return((a%n)-(b%n)+n)%n;
}
ll inv(ll a,ll n)
{
    return pow(a,n-2,n);
}
vector<ll> ff()
{
    int n=61;
    vector<ll> vv(n+1);
    vv[0]=2;
    ll j=2;
    for (int i=1;i<=n;i++)
    {
        vv[i]=0;
        vv[i]+=vv[i-1]+j;
        j*=2;
    }
    for (int i=1;i<=n;i++)
    {
        vv[i]+=vv[i-1];
    }
    return vv;
}
int xxxxx=2*1000000+1;
vector<ll> fact(xxxxx);
vector<ll> invfact(xxxxx);
void fac(ll n=mod)
{
    fact[0]=fact[1]=1;
    for (int i =2;i<xxxxx;i++)
        fact[i]=mult(fact[i-1],i,n);
}
void invfac(ll n=mod)
{
    invfact[xxxxx-1]=inv(fact[xxxxx-1],n);
    for (int i =xxxxx-2;i>=0;i--)
        invfact[i]=mult(invfact[i+1],i+1,n);
}
ll C(ll k,ll m,ll n=mod)
{
    if ((k>m)||(k<0))
        return 0;
    if (k==0)return 1;
    return mult(fact[m],mult(invfact[k],invfact[m-k],n),n);
}
void prep(ll n=mod)
{
    fac(n);
    invfac(n);
}
ll A(ll k, ll m, ll n)
{
    if ((k>m)||(k<0))
        return 1;
    return mult(fact[m],invfact[k],n);
}
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)





#define int long long


vector<int>g;
int n,a,b;
ll calc(ll i,ll j,segment_tree &st)
{
    if (j<0)return  0;
    if (i<0)i=0;
    return st.query(i,j)%mod;
}
void solve()
{
    cin>>n>>a>>b;
    ll q=0;
    for (int b1=0;b1<=b-n;b1++)
    {
        q+=C(b1,b1+n-1);
        q%=mod;
    }
    ll p=0;
    ll left=0+n-1,right=b-n+(n-1);
    g=vector<int>(right+1);
    for (int i=0;i<=right;++i)g[i]=C(n-1,i);
    st.init(right+1,g);
    for (int i=0;i<=n;++i)
    {
        int z=1;
        if(i&1)z=-1;
        p+=(z*C(i,n)*calc(left,right,st))%mod;
        left-=(a-n);
        right-=(a-n);
        p%=mod;
        if (p<0)p+=mod;
    }
    cout<<(p*pow(q,mod-2,mod))%mod<<endl;
}
signed  main() {
#ifndef ONLINE_JUDGE
    freopen("Error.txt", "w", stderr);
#endif

    fastio();
    int t;
    t=1;
    cin>>t;
    prep();
    while(t--)
    {
        solve();
    }
}
Leave a Comment