give_us_tmp/mod_int.cpp

/**
 * modint
 * 
 * 割り算やpowに関する物はO(log(mod))
 * それ以外はO(1)
 * 入出力可能
 * 
 */

template<uint mod>
struct modint{
    using M=modint;
    uint a;
    modint(ll x=0){set(x%mod+mod);}
    M& set(uint x){
        a = x<mod ? x : x-mod;
        return *this;
    }
    M operator-()const{return M()-*this;}
    M operator+(const M& x)const{return M().set(a+x.a);}
    M operator-(const M& x)const{return M().set(a-x.a+mod);}
    M operator*(const M& x)const{return M().set(ull(a)*x.a%mod);}
    M operator/(const M& x)const{return *this*x.inv();}
    M& operator+=(const M& x){return *this=*this+x;}
    M& operator-=(const M& x){return *this=*this-x;}
    M& operator*=(const M& x){return *this=*this*x;}
    M& operator/=(const M& x){return *this=*this/x;}
    bool operator==(const M& x)const{return a==x.a;}
    bool operator<(const M& x)const{return a<x.a;}
    M pow(ll n)const{
        M x=*this,r=1;
        while(n){
            if(n&1)r*=x;
            x*=x;
            n>>=1;
        }
        return r;
    }
    M inv()const{return pow(mod-2);}
    friend ostream& operator<<(ostream& os, const M& x){os<<x.a;return os;}
    friend istream& operator>>(istream& is,M& x){is>>x.a;return is;}
};

/**
 * combination
 * 
 * 前計算 :O(mx+log(mod))
 * 実行   :O(1)
 * Comb(n,k)        :n個からk個選ぶ
 * Comb::perm(n,k)  :n個から選ぶ順番を区別してk個選ぶ
 * Comb::fact(n)    :n!
 * Comb::ifact(n)   :1/n!
 * Comb::homo(n,k)  :n個から重複ありでk個選ぶ
 * 
 */

template<typename M>
struct Comb{
    static constexpr int mx=1'000'000;
    M fac[mx],ifac[mx];
    Comb(){
        fac[0]=1;
        for(int i=1;i<mx;++i){
            fac[i]=fac[i-1]*i;
        }
        ifac[mx-1]=fac[mx-1].inv();
        for(int i=mx-1;i>0;--i){
            ifac[i-1]=ifac[i]*i;
        }
    }
    M operator()(int n,int k){
        return fac[n]*ifac[k]*ifac[n-k];
    }
    M fact(int n){
        return fac[n];
    }
    M ifact(int n){
        return ifac[n];
    }
    M perm(int n,int k){
        return fac[n]*ifac[n-k];
    }
    M homo(int n,int k){
        return (*this)(n+k-1,k);
    }
};
using mint=modint<1000000007>;
Comb<mint>comb;

#line 1 "give_us_tmp/mod_int.cpp"
/**
 * modint
 * 
 * 割り算やpowに関する物はO(log(mod))
 * それ以外はO(1)
 * 入出力可能
 * 
 */

template<uint mod>
struct modint{
    using M=modint;
    uint a;
    modint(ll x=0){set(x%mod+mod);}
    M& set(uint x){
        a = x<mod ? x : x-mod;
        return *this;
    }
    M operator-()const{return M()-*this;}
    M operator+(const M& x)const{return M().set(a+x.a);}
    M operator-(const M& x)const{return M().set(a-x.a+mod);}
    M operator*(const M& x)const{return M().set(ull(a)*x.a%mod);}
    M operator/(const M& x)const{return *this*x.inv();}
    M& operator+=(const M& x){return *this=*this+x;}
    M& operator-=(const M& x){return *this=*this-x;}
    M& operator*=(const M& x){return *this=*this*x;}
    M& operator/=(const M& x){return *this=*this/x;}
    bool operator==(const M& x)const{return a==x.a;}
    bool operator<(const M& x)const{return a<x.a;}
    M pow(ll n)const{
        M x=*this,r=1;
        while(n){
            if(n&1)r*=x;
            x*=x;
            n>>=1;
        }
        return r;
    }
    M inv()const{return pow(mod-2);}
    friend ostream& operator<<(ostream& os, const M& x){os<<x.a;return os;}
    friend istream& operator>>(istream& is,M& x){is>>x.a;return is;}
};

/**
 * combination
 * 
 * 前計算 :O(mx+log(mod))
 * 実行   :O(1)
 * Comb(n,k)        :n個からk個選ぶ
 * Comb::perm(n,k)  :n個から選ぶ順番を区別してk個選ぶ
 * Comb::fact(n)    :n!
 * Comb::ifact(n)   :1/n!
 * Comb::homo(n,k)  :n個から重複ありでk個選ぶ
 * 
 */

template<typename M>
struct Comb{
    static constexpr int mx=1'000'000;
    M fac[mx],ifac[mx];
    Comb(){
        fac[0]=1;
        for(int i=1;i<mx;++i){
            fac[i]=fac[i-1]*i;
        }
        ifac[mx-1]=fac[mx-1].inv();
        for(int i=mx-1;i>0;--i){
            ifac[i-1]=ifac[i]*i;
        }
    }
    M operator()(int n,int k){
        return fac[n]*ifac[k]*ifac[n-k];
    }
    M fact(int n){
        return fac[n];
    }
    M ifact(int n){
        return ifac[n];
    }
    M perm(int n,int k){
        return fac[n]*ifac[n-k];
    }
    M homo(int n,int k){
        return (*this)(n+k-1,k);
    }
};
using mint=modint<1000000007>;
Comb<mint>comb;