曾经发明了脑洞治疗仪&超能粒子炮的发明家SHTSC又公开了他的新发明：超能粒子炮·改--一种可以发射威力更加

强大的粒子流的神秘装置。超能粒子炮·改相比超能粒子炮，在威力上有了本质的提升。它有三个参数n，k。它会

向编号为0到k的位置发射威力为C(n,k) mod 2333的粒子流。现在SHTSC给出了他的超能粒子炮·改的参数，让你求

其发射的粒子流的威力之和模2333。

第一行一个整数t。表示数据组数。

之后t行，每行二个整数n，k。含义如题面描述。

k<=n<=10^18，t<=10^5

t行每行一个整数，表示其粒子流的威力之和模2333的值。

同类项合并，分两种部分考虑：

设k=k1*2333+k2 (0≤k1,k2)

1)对于k1部分

先考虑k1=0的情况，可以得出这些乘积的各个首项是C(n/2333,0)，将其提出得到C(n/2333,0)*∑C(n%2333,i)(其中i∈[0,2333])

考虑k1=1的情况，可得C(n/2333,1)*∑C(n%2333,i)(其中i∈[0,2333])

考虑k1=2的情况，可得C(n/2333,2)*∑C(n%2333,i)(其中i∈[0,2333])

···　　···　　···　　···　　···　　···

提公因式→→→∑C(n/2333,j)*∑C(n%2333,i)(其中i∈[0,2333],j∈[0,k1))

重复3遍

∑C(n/2333,j)*∑C(n%2333,i)(其中i∈[0,2333],j∈[0,k1))

∑C(n/2333,j)*∑C(n%2333,i)(其中i∈[0,2333],j∈[0,k1))

∑C(n/2333,j)*∑C(n%2333,i)(其中i∈[0,2333],j∈[0,k1))

吼，各位就等了，看看k2部分吧

2）对于k2部分

原式=C(n/2333,k1)*C(n%2333,0)+C(n/2333,k1)*C(n%2333,1)+······+C(n/2333,k1)*C(n%2333,k%2333)

=C(n/2333,k1)*(∑C(n%2333,i))(其中i∈[0,k%2333])

综上，ans=∑C(n/2333,j)*∑C(n%2333,i)(其中i∈[0,2333],j∈[0,k1))+C(n/2333,k1)*(∑C(n%2333,i))(其中i∈[0,k%2333])

 

说了这么多，那么这个定理的用法是什么？

显然是递归求解组合数的模数咯～

 

#include <stdio.h>

#include <string.h>

#define md 2333

#define LL long long

inline LL Rin() {

  LL x=,c=getchar();

  for(;c<||c>;c=getchar());

  for(;c>&&c<;c=getchar())

    x=x*+c-(LL);

  return x; }

inline LL mod(LL x) {

  return x-(x/md)*md; }

LL frac[md+],c[md+][md+],s[md+][md+];

void calc() {

  frac[]=1LL;

  for(int i=;i<=md;i++)

    frac[i]=mod(frac[i-]*(LL)i);

  c[][]=1LL;

  for(int i=;i<=md;i++) {

    c[i][]=c[i][i]=1LL;

    for(int j=;j<i;j++)

      c[i][j]=mod(c[i-][j-]+c[i-][j]); }

  for(int i=;i<=md;i++) {

    s[i][]=1LL;

    for(int j=;j<=md;j++)

      s[i][j]=mod(s[i][j-]+c[i][j]); } }

LL lucas(LL n,LL k) {

  return k!=0LL?mod(c[n%md][k%md]*lucas(n/md,k/md)):1LL; }

LL getans(LL n,LL k) {

  return k<0LL?0LL:mod(mod(s[mod(n)][md-]*getans(n/md,k/md-))+mod(lucas(n/md,k/md)*s[mod(n)][mod(k)])); }

int main() {

  calc();

  LL n,k,T=Rin();

  while(T--)

    n=Rin(),k=Rin(),printf("%lld\n",getans(n,k));

  return ; }