const int MO=1e9+7;
inline int add(int x,int y) { x+=y; if(x>=MO) x-=MO; return x; }
inline int sub(int x,int y) { x-=y; if(x<0) x+=MO; return x; }
inline int mul(int x,int y) { return 1LL*x*y%MO; }
inline void addv(int &x,int y) { x+=y; if(x>=MO) x-=MO; }
inline void subv(int &x,int y) { x-=y; if(x<0) x+=MO; }
inline void mulv(int &x,int y) { x=1LL*x*y%MO; }
int qp(int x,int n)
{
    int ans=1;
    while(n) { if(n&1) { mulv(ans,x); } mulv(x,x); n>>=1; }
    return ans;
}

template<int MO=1000000007>
struct ModInt
{
    int x;
    ModInt(int x=0):x(x){ norm(); }
    void read() { scanf("%d",&x); }
    void print() { printf("%d",x); }
    friend istream &operator>>(istream& in, ModInt &B) { in>>B.x; return in; }
    friend ostream &operator<<(ostream& out, const ModInt &B) { out<<B.x; return out; }
    ModInt operator=(int x_) { x=x_; norm(); return *this; }
    void norm() { x=(x%MO+MO)%MO; }
    int get() { return x; }

    ModInt operator+(const ModInt &B) const { int ans=x+B.x; if(ans>=MO) ans-=MO; return ModInt(ans); }
    ModInt operator-(const ModInt &B) const { int ans=x-B.x; if(ans<0) ans+=MO; return ModInt(ans); }
    ModInt operator*(const ModInt &B) const { int ans=1LL*x*B.x%MO; return ModInt(ans); }
    ModInt operator+=(const ModInt &B) { x+=B.x; if(x>=MO) x-=MO; return *this; }
    ModInt operator-=(const ModInt &B) { x-=B.x; if(x<0) x+=MO; return *this; }
    ModInt operator*=(const ModInt &B) { x=1LL*x*B.x%MO; return *this; }
    ModInt operator^(int n) const 
    {
        ModInt a=*this,ans(1);
        while(n) { if(n&1) ans*=a; a*=a; n>>=1; }
        return ans;
    }
    
    bool operator==(int b) const { return x==b; }
    bool operator!=(int b) const { return x!=b; }
    bool operator==(const ModInt &B) const { return x==B.x; }
    bool operator!=(const ModInt &B) const { return x!=B.x; }

    ModInt inv() const { return this^(MO-2); } // if MO is prime
};
typedef ModInt<> Mint;

using LL = long long;
template<LL MO=1000000007>
struct ModInt
{
    LL x;
    ModInt(LL x=0):x(x){ norm(); }
    void read() { scanf("%lld",&x); }
    void print() { printf("%lld",x); }
    friend istream &operator>>(istream& in, ModInt &B) { in>>B.x; norm(); return in; }
    friend ostream &operator<<(ostream& out, const ModInt &B) { out<<B.x; return out; }
    ModInt operator=(LL x_) { x=x_; norm(); return *this; }
    void norm() { x=(x%MO+MO)%MO; }
    LL get() { return x; }

    ModInt operator+(const ModInt &B) const { LL ans=x+B.x; if(ans>=MO) ans-=MO; return ModInt(ans); }
    ModInt operator-(const ModInt &B) const { LL ans=x-B.x; if(ans<0) ans+=MO; return ModInt(ans); }
    ModInt operator+=(const ModInt &B) { x+=B.x; if(x>=MO) x-=MO; return *this; }
    ModInt operator-=(const ModInt &B) { x-=B.x; if(x<0) x+=MO; return *this; }
    ModInt operator*=(const ModInt &B) {
        LL a=x,n=B.x,ans=0;
        while(n)
        { 
            if(n&1) { ans+=a; if(ans>=MO) ans-=MO;} 
            a+=a; if(a>=MO) a-=MO; n>>=1; 
        }
        x=ans;
        return *this;
    }
    ModInt operator*(const ModInt &B) const { ModInt ans=*this; return ans*=B; }
    ModInt operator^(LL n) const 
    {
        ModInt a=*this,ans(1);
        while(n) { if(n&1) ans*=a; a*=a; n>>=1; }
        return ans;
    }
    
    bool operator==(LL b) const { return x==b; }
    bool operator!=(LL b) const { return x!=b; }
    bool operator==(const ModInt &B) const { return x==B.x; }
    bool operator!=(const ModInt &B) const { return x!=B.x; }

    ModInt inv() const { return this^(MO-2); } // if MO is prime
};
typedef ModInt<> Mint;