24 mint operator+(mint x, mint y) { return x+=y; } 24 mint operator+(mint x, mint y) { return x+=y; } 25 mint operator-(mint x, mint y) { return x-=y; } 25 mint operator-(mint x, mint y) { return x-=y; } 26 mint operator*(mint x, mint y) { return x*=y; } 26 mint operator*(mint x, mint y) { return x*=y; } 27 mint operator/(mint x, mint y) { return x/=y; } 27 mint operator/(mint x, mint y) { return x/=y; } 28 vector<mint> FAC_(1,1); 28 vector<mint> FAC_(1,1); 29 mint FAC(LL n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*FAC_.size() 29 mint FAC(LL n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*FAC_.size() 30 mint C(LL n, LL k) { return k<0 || n<k ? 0 : FAC(n) / (FAC(k) * FAC(n-k)); } 30 mint C(LL n, LL k) { return k<0 || n<k ? 0 : FAC(n) / (FAC(k) * FAC(n-k)); } 31 < 32 // Pascal's triangle: if O(1) nCk is needed. | 31 vector< vector<mint> > CP_; // Pascal's triangle: if O(1) nCk is needed. 33 vector< vector<mint> > CP_(2001); < 34 mint C(LL n, LL k) { 32 mint C(LL n, LL k) { 35 if(CP_[0].empty()) { | 33 while( CP_.size() <= n ) { 36 CP_[0].push_back(1); < 37 for(int nn=1; nn<CP_.size(); ++nn) | 34 int nn = CP_.size(); > 35 CP_.push_back(vector<mint>(nn+1,1)); 38 for(int kk=0; kk<=nn; ++kk) | 36 for(int kk=1; kk<nn; ++kk) 39 CP_[nn].push_back( (kk?CP_[nn-1][kk-1]:0) + (kk<nn?CP_[n | 37 CP_[nn][kk] = CP_[nn-1][kk-1] + CP_[nn-1][kk]; 40 } 38 } 41 return k<0 || n<k ? 0 : CP_[n][k]; 39 return k<0 || n<k ? 0 : CP_[n][k]; 42 } 40 } 43 < 44 < 45 41 46 /* 42 /* 47 // MODVAL must be a prime!! 43 // MODVAL must be a prime!! 48 LL GSS(LL k, LL b, LL e) // k^b + k^b+1 + ... + k^e 44 LL GSS(LL k, LL b, LL e) // k^b + k^b+1 + ... + k^e 49 { 45 { 50 if( b > e ) return 0; 46 if( b > e ) return 0; 51 if( k <= 1 ) return k*(e-b+1); 47 if( k <= 1 ) return k*(e-b+1);