$$\sum\limits_{i=0}^{k}C_{n}^{i} \mathbin{\mathrm{mod}} 2333$$

\begin{aligned} f(n,k)&=\sum\limits_{i=0}^{k}C_{n}^{i} \mathbin{\mathrm{mod}} p\\ &=\sum\limits_{i=0}^{k}C_{n\%p}^{i\%p}\cdot C_{n/p}^{i/p} \mathbin{\mathrm{mod}} p\\ &=\sum\limits_{x=0}^{p-1}C_{n\%p}^{x}\cdot \sum_{i=0}^{k}[i\%p=x]C_{n/p}^{i/p} \mathbin{\mathrm{mod}} p\\ &=C_{n/p}^{0}\sum\limits_{x=0}^{p-1}C_{n\%p}^{x}+C_{n/p}^{1}\sum\limits_{x=0}^{p-1}C_{n\%p}^{x}\cdots C_{n/p}^{k/p}\sum\limits_{x=0}^{k\%p} C_{n\%p}^{x}\mathbin{\mathrm{mod}}p\\ &=\sum\limits_{i=0}^{k/p-1}C_{n/p}^{i}\cdot \sum\limits_{x=0}^{p-1}C_{n\%p}^{x}+C_{n/p}^{k/p}\sum\limits_{x=0}^{k\%p}C_{n\%p}^{x}\mathbin{\mathrm{mod}}p\\ &=f(n/p,k/p-1)\cdot f(n\%p,p-1)+C_{n/p}^{k/p}\cdot f(n\%p,k\%p)\mathbin{\mathrm{mod}}p\\ \end{aligned}

### Code：

#include <queue>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=2333+2;
#define p 2333

ll n,k,f[N][N],c[N][N];

template <typename _Tp> inline void IN(_Tp&x) {
char ch;bool flag=0;x=0;
while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
if(flag) x=-x;
}

ll lucas(ll n,ll m) {
if(!m||n==m) return 1;
if(n<m) return 0;
if(n<p&&m<p) return c[n][m];
return c[n%p][m%p]*lucas(n/p,m/p)%p;
}
ll F(ll n,ll k) {
if(k<0) return 0;
if(!n||!k) return 1;
if(n<p&&k<p) return f[n][k];
return (F(n/p,k/p-1)*f[n%p][p-1]%p+lucas(n/p,k/p)*f[n%p][k%p]%p)%p;
}

int main() {
for(int i=0;i<=p;++i) c[i][0]=c[i][i]=1,f[i][0]=1;
for(int i=1;i<=p;++i) for(int j=1;j<i;++j)
c[i][j]=(c[i-1][j]+c[i-1][j-1])%p;
for(int i=0;i<=p;++i) for(int j=1;j<=p;++j)
f[i][j]=(f[i][j-1]+c[i][j])%p;
int t;IN(t);
while(t--) {
IN(n),IN(k);
printf("%lld\n",F(n,k));
}
return 0;
}


QAQ