$\sum\limits_{i=0}^kC_{n}^i=\sum\limits_{i=0}^k C_{n/2333}^{i/2333}*C_{n\text{%}2333}^{i\text{%}2333} $

发现$i/2333$变化很慢,可以转化成$k=a*2333+b(b<2333)$的形式。

于是

$\sum\limits_{i=0}^k C_{n/2333}^{i/2333}*C_{n\text{%}2333}^{i\text{%}2333}=\sum\limits_{i=0}^{\lfloor\frac{k}{2333}\rfloor-1}C_{n/2333}^i*\sum\limits_{j=0}^{2332}C_{n\text{%}2333}^j+\sum\limits_{i=0}^{k\text{%}2333}C_{n\text{%}2333}^i*C_{n/2333}^{\lfloor\frac{k}{2333}\rfloor}$

令$S_{n}^k=\sum_{i=0}^k C_{n}^i$

则答案为

$S_{n/2333}^{\lfloor\frac{k}{2333}\rfloor-1}*S_{n\text{%}2333}^{2332}+S_{n\text{%}2333}^{k\text{%}2333}*C_{n/2333}^{\lfloor\frac{k}{2333}\rfloor}$

注意$n\text{%}2333<2332$的情况。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define gc getchar()
#define ll long long
using namespace std;
const int N=2e5+5,mod=2333,M=1e6;
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>
void qw(o x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int s[mod+5][mod+5],p[mod+5],inv[mod+5];
inline int fpow(int a,int b){int ans=1;for(;b;b>>=1,a=a*a%mod)if(b&1)ans=ans*a%mod;return ans;}
inline int lucas(ll n,ll m)
{
    int a,b,ret=1;
    for(;n&&m;n/=mod,m/=mod)
    {
        a=n%mod,b=m%mod;
        if(a<b)return 0;
        ret=ret*p[a]%mod*inv[b]%mod*inv[a-b]%mod;
    }
    return ret;
}
inline int calc(ll n,ll k)
{
    if(n<mod&&k<mod)return s[n][k];
    int ret=s[n%mod][k%mod]*lucas(n/mod,k/mod)%mod;
    if(k>=mod)ret=ret+calc(n/mod,k/mod-1)*s[n%mod][mod-1]%mod;
    return ret%mod;
}
int main()
{
    p[0]=1;for(int i=1;i<mod;i++)p[i]=p[i-1]*i%mod;
    inv[mod-1]=fpow(p[mod-1],mod-2);
    inv[0]=1;for(int i=mod-2;i>=1;i--)inv[i]=inv[i+1]*(i+1)%mod;
    for(int i=0;i<mod;i++)
    {
        s[i][0]=1;for(int j=1;j<=i;j++)s[i][j]=(lucas(i,j)+s[i][j-1])%mod;
        for(int j=i+1;j<mod;j++)s[i][j]=s[i][j-1];
    }
    int T;qr(T);
    while(T--)
    {
        ll n,k;qr(n),qr(k);
        qw(calc(n,k));puts("");
    }
    return 0;
}