constexpr int mod = 1e9+7;
struct mint {
    // inner value
    long long v;

    // constructor
    constexpr mint() : v(0) { }
    constexpr mint(long long v) : v(v % mod) {
        if (v < 0) v += mod;
    }
    constexpr long long get() const { return v; }
    constexpr int get_mod() const { return mod; }
    explicit operator int() const { return v; }

    // arithmetic operators
    constexpr mint operator + () const { return *this; }
    constexpr mint operator - () const { return v ? mint(mod - v) : mint(0); }
    friend constexpr mint operator + (mint l, const mint &r) { return l += r; }
    friend constexpr mint operator - (mint l, const mint &r) { return l -= r; }
    friend constexpr mint operator * (mint l, const mint &r) { return l *= r; }
    friend constexpr mint operator / (mint l, const mint &r) { return l /= r; }
    constexpr mint& operator += (const mint &r) {
        v += r.v;
        if (v >= mod) v -= mod;
        return *this;
    }
    constexpr mint& operator -= (const mint &r) {
        v -= r.v;
        if (v < 0) v += mod;
        return *this;
    }
    constexpr mint& operator *= (const mint &r) {
        v = v * r.v % mod;
        return *this;
    }
    constexpr mint& operator /= (const mint &r) {
        return *this *= r.inv();
    }
    constexpr mint pow(long long n) const {
        mint res(1), mul(*this);
        while (n > 0) {
            if (n & 1) res *= mul;
            mul *= mul;
            n >>= 1;
        }
        return res;
    }
    constexpr mint inv() const {
        return pow(mod - 2);
    }
    constexpr int legendre() const {
        int res = pow(mod >> 1).v;
        return (res == mod - 1) ? -1 : res;
    }

    // Square root (https://judge.yosupo.jp/submission/122087)
    std::optional<mint> sqrt() const {
        mint a(*this);
        int m = mod;
        if(a.v < 2) return a;
        if(m % 2 == 0 || a.pow(m >> 1) == -1) return nullopt;
        static mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
        mint t;
        do t = rnd(); while((t*t - a*4).pow(m >> 1) != -1);
        mint d = 1, c = -t, b = -t;
        for (++m; m >>= 1; b = a*2 - b*b, a *= a) {
            if (m % 2) d = c - d*b, c *= a;
            else c = d*a - c*b;
        }
        if (2*d.v > mod) return -d;
        return d;
    }

    // @warning a must not contain a 0
    friend vector<mint> invs(const vector<mint> &a) {
        int n = a.size();
        vector<mint> b(n+1);
        b[0] = 1;
        for (int i = 0; i < n; i++) b[i+1] = b[i] * a[i];
        assert(b[n] != 0);
        mint x = b[n].inv();
        vector<mint> res(n);
        for (int i = n-1; i >= 0; i--) {
            res[i] = x * b[i];
            x *= a[i];
        }
        return res;
    }

    // combo
    inline static vector<int> facts{1}, finvs{1};
    friend mint fact(mint a) {
        while (facts.size() <= a.v) {
            facts.push_back((int64_t)facts.back() * facts.size() % mod);
        }
        return facts[a.v];
    }
    friend mint finv(mint a) {
        while (finvs.size() <= a.v) finvs.push_back(fact((mint)finvs.size()).inv().v);
        return finvs[a.v];
    }
    friend mint choose(mint n, mint k) {
        return fact(n) * finv(k) * finv(n - k);
    }
    friend mint perm(mint n, mint k) {
        return fact(n) * finv(n - k);
    }
    static void precomp_fact(int n) {
        fact(mint(n));
        int old = finvs.size();
        if (old > n) return;
        finvs.resize(n + 1);
        finvs[n] = mint(facts[n]).inv().v;
        for (int i = n; i >= old; i--)
            finvs[i - 1] = (int64_t)finvs[i] * i % mod;
    }

    // other operators
    constexpr bool operator == (const mint &r) const {
        return this->v == r.v;
    }
    constexpr bool operator != (const mint &r) const {
        return this->v != r.v;
    }
    constexpr mint& operator ++ () {
        ++v;
        if (v >= mod) v -= mod;
        return *this;
    }
    constexpr mint& operator -- () {
        if (v == 0) v += mod;
        --v;
        return *this;
    }
    constexpr mint operator ++ (int) {
        mint res = *this;
        ++*this;
        return res;
    }
    constexpr mint operator -- (int) {
        mint res = *this;
        --*this;
        return res;
    }
    friend istream& operator >> (istream &is, mint &x) {
        is >> x.v;
        x.v %= mod;
        if (x.v < 0) x.v += mod;
        return is;
    }
    friend ostream& operator << (ostream &os, const mint &x) {
        return os << x.v;
    }
    friend constexpr mint pow(const mint &r, long long n) {
        return r.pow(n);
    }
    friend constexpr mint inv(const mint &r) {
        return r.inv();
    }
    friend constexpr mint legendre(const mint &r) {
        return r.legendre();
    }
    friend optional<mint> sqrt(const mint &r) {
        return r.sqrt();
    }
};