7 //------------------------------------------------------------- 7 //------------------------------------------------------------- 8 8 9 static const int MODVAL = 1000000007; // must be prime for op/ 9 static const int MODVAL = 1000000007; // must be prime for op/ 10 struct mint 10 struct mint 11 { 11 { 12 int val; 12 int val; 13 mint():val(0){} 13 mint():val(0){} > 14 mint(int x):val(x%MODVAL) {} // x>=0 14 mint(int x):val(x%MODVAL) {} | 15 mint(size_t x):val(x%MODVAL) {} // x>=0 15 mint(LL x):val(x%MODVAL) {} | 16 mint(LL x):val(x%MODVAL) {} // x>=0 16 }; 17 }; > 18 mint& operator+=(mint& x, mint y) { return x = x.val+y.val; } > 19 mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; } > 20 mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; } > 21 mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; } > 22 mint& operator/=(mint& x, mint y) { return x *= POW(y, MODVAL-2); } 17 mint operator+(mint x, mint y) { return x.val+y.val; } | 23 mint operator+(mint x, mint y) { return x+=y; } 18 mint operator-(mint x, mint y) { return x.val-y.val+MODVAL; } | 24 mint operator-(mint x, mint y) { return x-=y; } 19 mint operator*(mint x, mint y) { return LL(x.val)*y.val; } | 25 mint operator*(mint x, mint y) { return x*=y; } 20 mint POW(mint x, int e) { < 21 mint v = 1; < 22 for(;e;x=x*x,e>>=1) < 23 if(e&1) < 24 v=v*x; < 25 return v; | 26 mint operator/(mint x, mint y) { return x/=y; } > 27 vector<mint> FAC_(1,1); > 28 mint FAC(LL n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*FAC_.size() > 29 mint C(LL n, LL k) { return k<0 || n<k ? 0 : FAC(n) / (FAC(k) * FAC(n-k)); } 26 } | 30 27 mint operator/(mint x, mint y) { return x * POW(y, MODVAL-2); } < 28 31 29 vector<mint> FAC_(1,1); < 30 void FAC_INIT(int n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*FAC_. < 31 mint FAC(mint x) { return FAC_[x.val]; } < 32 mint C(mint n, mint k) { return k.val<0 || n.val<k.val ? 0 : FAC(n) / (FAC(k) * < > 32 33 33 34 /* 34 /* 35 // MODVAL must be a prime!! 35 // MODVAL must be a prime!! 36 LL GSS(LL k, LL b, LL e) // k^b + k^b+1 + ... + k^e 36 LL GSS(LL k, LL b, LL e) // k^b + k^b+1 + ... + k^e 37 { 37 { 38 if( b > e ) return 0; 38 if( b > e ) return 0; 39 if( k <= 1 ) return k*(e-b+1); 39 if( k <= 1 ) return k*(e-b+1);