代码
```cpp
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <ctime>
#define int long long
using namespace std;
const int mod=2333;
int n,m,ans,jc[20000010],inv[20000010],sum[20000010];
int C(int n,int m){
if(n<m)return 0;
return 1ll*jc[n]*inv[m]%mod*inv[n-m]%mod;
}
int lucas(int n,int m){
if(m==0)return 1;
return C(n%mod,m%mod)*lucas(n/mod,m/mod)%mod;
}
int solve(int n,int m){
int ans=0;
if(m<mod){
for(int i=0;i<=m;i++)ans=(ans+lucas(n,i))%mod;
return ans;
}
sum[0]=1;
for(int i=1;i<mod;i++)sum[i]=(sum[i-1]+C(n%mod,i))%mod;
int ret=m%mod;
ans=(1ll*sum[ret]*solve(n/mod,m/mod)%mod+1ll*(sum[n%mod]-sum[ret]+mod)*solve(n/mod,m/mod-1)%mod)%mod;
return ans;
}
signed main(){
int tim;scanf("%lld",&tim);
jc[0]=inv[0]=jc[1]=inv[1]=1;
for(int i=2;i<mod;i++)jc[i]=1ll*jc[i-1]*i%mod,inv[i]=(mod-mod/i)*inv[mod%i]%mod;
for(int i=1;i<mod;i++)inv[i]=1ll*inv[i-1]*inv[i]%mod;
while(tim--){
scanf("%lld%lld",&n,&m);
printf("%lld\n",solve(n,m));
}
return 0;
}
```
by worldvanquisher @ 2022-11-21 15:20:02