AC x1 WA x2 TLE x3

能过样例

// Date: 2023-10-12 14:29:41
// Problem: 高橋君
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/AT_tenka1_2014_final_d
// Memory Limit: 256 MB
// Time Limit: 6000 ms

// clang-format off
#include <bits/stdc++.h>
// #define int long long
#define debug(x) cout<<#x": "<<x<<endl;
#define endl '\n'
#define F(i,l,r) for(int i=l;i<r;++i)
#define Fe(i,l,r) for(int i=l;i<=r;++i)
#define Fer(i,l,r) for(int i=l;i>=r;--i)
#define sFe(i,l,r) for(int i=l,_##i=r;i<=_##i;++i) 
#define sFer(i,r,l) for(int i=r,_##i=l;i>=_##i;--i)
#define sF(i,l,r) for(int i=l,_##i=r;i<_##i;++i)
#define chmax(a,b) if((a)<(b)){(a)=(b);}
#define chmin(a,b) if((a)>(b)){(a)=(b);}
#define nli(i,n) " \n"[(i)==(n)]
#define mecpy(a,b) memcpy(a,b,sizeof(a))
#define meset(a,b) memset(a,b,sizeof(a))
#define reopen(x) { freopen(#x".in","r",stdin);freopen(#x".out","w",stdout); }
#define by(x) [](const auto&a,const auto&b) {return a.x<b.x;}
#define __TIME_COUNT std::chrono::steady_clock::now().time_since_epoch().count()
using namespace std;
typedef long long ll;
mt19937 _rnd(__TIME_COUNT);
auto rnd(ll l,ll r){return std::uniform_int_distribution<ll>(l,r)(_rnd);}
ll startTime=__TIME_COUNT;
inline double getCurrentTime(){return (double)(__TIME_COUNT-startTime)/1000000;}
inline void fastio(){ios::sync_with_stdio(false);cin.tie(nullptr);}
// clang-format on

constexpr int N = 100000, mod = 1000000007, siz = 320;
int n, k;
int fac[N + 5], ifac[N + 5];
int T;
int nowk, nown;
ll ans;
int bc[N + 5], ANS[N + 5];

struct QUE{
    int n, k, id;
    bool operator < (const QUE &o) const {
        return bc[n] == bc[o.n] ? bc[n] < bc[o.n] : k < o.k;
    }
} q[N + 5];

int qpow(int a, int b, int p){
    int res = 1;
    while(b){
        if(b & 1) res = 1ll * res * a % p;
        b >>= 1;
        a = 1ll * a * a % p;
    }
    return res;
}

void init(){
    fac[0] = 1;
    Fe(i, 1, N) fac[i] = 1ll * fac[i - 1] * i % mod;
    ifac[N] = qpow(fac[N], mod - 2, mod);
    Fer(i, N - 1, 0) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % mod;
    // Fe(i, 1, 1000) cout << 1ll * fac[i] * ifac[i] % mod << endl;
    Fe(i, 1, N) bc[i] = (i - 1) / siz + 1;
}

int C(int a, int b) {
    return 1ll * fac[a] * ifac[a - b] % mod * ifac[b] % mod;
}

void addk(){
    ans = (ans + C(nown, nowk + 1)) % mod;
    ++ nowk;
}

void subk(){
    ans = ((ans - C(nown, nowk)) % mod + mod) % mod;
    -- nowk;
}

void addn(){
    ans = ((ans * 2 % mod - C(nown, nowk)) % mod + mod) % mod;
    ++ nown;
}

void subn(){
    ans = (ans + C(nown - 1, nowk)) % mod * ifac[2] % mod;
    -- nown;
}

void solve(){
    init();
    Fe(i, 1, T) cin >> q[i].n >> q[i].k;
    Fe(i, 1, T) q[i].id = i;
    sort(q + 1, q + T + 1);
    nown = 1; nowk = 0; ans = 1;
    Fe(i, 1, T){
        while(nown < q[i].n) addn();
        while(nown > q[i].n) subn();
        while(nowk < q[i].k) addk();
        while(nowk > q[i].k) subk();
        ANS[q[i].id] = ans;
    }
    Fe(i, 1, T) cout << ANS[i] << endl;
}

void BF(){
    init();
    while(T--){
        cin >> n >> k;
        ll ans = 0;
        Fe(i, 0, k) {
            ans = (ans + C(n, i)) % mod;
        }
        cout << ans % mod << endl;
    }
}

signed main(){
    fastio();
    cin >> T;
    solve();
}