ModInt

template <typename T>
constexpr T power(T a, long long b) {
  T res {1};
  for (; b > 0; a *= a, b >>= 1) {
    if (b & 1) {
      res *= a;
    }
  }
  return res;
}

constexpr bool isPrime(long long x) {
  for (int i = 2; 1LL * i * i <= x; ++i) {
    if (x % i == 0) {
      return false;
    }
  }
  return true;
}

template <int mod>
struct ModInt {
  int x;

  static constexpr int getNorm(long long x) {
    if (x < -mod || mod <= x) {
      x %= mod;
    }
    if (x < 0) {
      x += mod;
    }
    return int(x);
  }

  static constexpr int getInversed(long long x) {
    x = getNorm(x);
    if constexpr (isPrime(mod)) {
      return int(power(ModInt(x), mod - 2));
    } else {
      long long m = mod;
      long long u = 1;
      long long v = 0;
      while (m != 0) {
        int t = x / m;
        x -= t * m;
        u -= t * v;
        std::swap(x, m);
        std::swap(u, v);
      }
      return getNorm(u);
    }
  }

  /* implicit */ constexpr ModInt(long long y = 0) : x(getNorm(y)) {
    static_assert(mod <= std::numeric_limits<int>::max() / 2);
    void(0);
  }

  template <typename T>
  constexpr explicit operator T () const {
    return x;
  }

  constexpr ModInt operator-() const {
    return x == 0 ? 0 : mod - x;
  }

  constexpr ModInt& operator+=(const ModInt& ot) {
    if ((x += ot.x) >= mod) {
      x -= mod;
    }
    return *this;
  }

  constexpr friend ModInt operator+(const ModInt& a, const ModInt& b) {
    ModInt res = a;
    return res += b;
  }

  constexpr ModInt& operator-=(const ModInt& ot) {
    if ((x -= ot.x) < 0) {
      x += mod;
    }
    return *this;
  }

  constexpr friend ModInt operator-(const ModInt& a, const ModInt& b) {
    ModInt res = a;
    return res -= b;
  }

  constexpr ModInt& operator*=(const ModInt& ot) {
    x = int(1LL * x * ot.x % mod);
    return *this;
  }

  constexpr friend ModInt operator*(const ModInt& a, const ModInt& b) {
    ModInt res = a;
    return res *= b;
  }

  constexpr ModInt& operator/=(const ModInt& ot) {
    x = int(1LL * x * getInversed(ot.x) % mod);
    return *this;
  }

  constexpr friend ModInt operator/(const ModInt& a, const ModInt& b) {
    ModInt res = a;
    return res /= b;
  }

  constexpr friend bool operator==(const ModInt& a, const ModInt& b) {
    return int(a) == int(b);
  }

  constexpr friend bool operator!=(const ModInt& a, const ModInt& b) {
    return int(a) != int(b);
  }

  constexpr friend bool operator<(const ModInt& a, const ModInt& b) {
    return int(a) < int(b);
  }

  constexpr friend bool operator<=(const ModInt& a, const ModInt& b) {
    return int(a) <= int(b);
  }

  constexpr friend bool operator>(const ModInt& a, const ModInt& b) {
    return int(a) > int(b);
  }

  constexpr friend bool operator>=(const ModInt& a, const ModInt& b) {
    return int(a) >= int(b);
  }

  friend std::istream& operator>>(std::istream& stream, ModInt& x) {
    long long t;
    stream >> t;
    x = t;
    return stream;
  }

  friend std::ostream& operator<<(std::ostream& stream, const ModInt& x) {
    return stream << int(x);
  }
};

struct DynamicModInt {
  static int mod;
  int x;

  static int getNorm(long long x) {
    assert(mod > 0);
    if (x < -mod || mod <= x) {
      x %= mod;
    }
    if (x < 0) {
      x += mod;
    }
    return int(x);
  }

  static int getInversed(long long x) {
    x = getNorm(x);
    long long m = mod;
    long long u = 1;
    long long v = 0;
    while (m != 0) {
      int t = int(x / m);
      x -= t * m;
      u -= t * v;
      std::swap(x, m);
      std::swap(u, v);
    }
    assert(x == 1);
    return getNorm(u);
  }

  /* implicit */ DynamicModInt(long long y = 0) : x(getNorm(y)) {
    void(0);
  }

  template <typename T>
  explicit operator T() const {
    return x;
  }

  DynamicModInt operator-() const {
    return x == 0 ? 0 : mod - x;
  }

  DynamicModInt& operator+=(const DynamicModInt& ot) {
    if ((x += ot.x) >= mod) {
      x -= mod;
    }
    return *this;
  }

  friend DynamicModInt operator+(const DynamicModInt& a, const DynamicModInt& b) {
    DynamicModInt res = a;
    return res += b;
  }

  DynamicModInt& operator-=(const DynamicModInt& ot) {
    if ((x -= ot.x) < 0) {
      x += mod;
    }
    return *this;
  }

  friend DynamicModInt operator-(const DynamicModInt& a, const DynamicModInt& b) {
    DynamicModInt res = a;
    return res -= b;
  }

  DynamicModInt& operator*=(const DynamicModInt& ot) {
    x = int(1LL * x * ot.x % mod);
    return *this;
  }

  friend DynamicModInt operator*(const DynamicModInt& a, const DynamicModInt& b) {
    DynamicModInt res = a;
    return res *= b;
  }

  DynamicModInt& operator/=(const DynamicModInt& ot) {
    x = int(1LL * x * getInversed(ot.x) % mod);
    return *this;
  }

  friend DynamicModInt operator/(const DynamicModInt& a, const DynamicModInt& b) {
    DynamicModInt res = a;
    return res /= b;
  }

  friend bool operator==(const DynamicModInt& a, const DynamicModInt& b) {
    return int(a) == int(b);
  }

  friend bool operator!=(const DynamicModInt& a, const DynamicModInt& b) {
    return int(a) != int(b);
  }

  friend bool operator<(const DynamicModInt& a, const DynamicModInt& b) {
    return int(a) < int(b);
  }

  friend bool operator<=(const DynamicModInt& a, const DynamicModInt& b) {
    return int(a) <= int(b);
  }

  friend bool operator>(const DynamicModInt& a, const DynamicModInt& b) {
    return int(a) > int(b);
  }

  friend bool operator>=(const DynamicModInt& a, const DynamicModInt& b) {
    return int(a) >= int(b);
  }

  friend std::istream& operator>>(std::istream& stream, DynamicModInt& x) {
    long long t;
    stream >> t;
    x = t;
    return stream;
  }

  friend std::ostream& operator<<(std::ostream& stream, const DynamicModInt& x) {
    return stream << int(x);
  }
};

 

FUCKING KOISTUDY VERSION

 

template <int mod>
struct ModInt {
  int x;

  int getNorm(long long x) {
    if (x < -mod || mod <= x) {
      x %= mod;
    }
    if (x < 0) {
      x += mod;
    }
    return int(x);
  }

  int getInversed(long long x) {
    x = getNorm(x);
    if (true) {
      return int(power(ModInt(x), mod - 2));
    } else {
      long long m = mod;
      long long u = 1;
      long long v = 0;
      while (m != 0) {
        int t = x / m;
        x -= t * m;
        u -= t * v;
        std::swap(x, m);
        std::swap(u, v);
      }
      return getNorm(u);
    }
  }

  ModInt(long long y = 0) : x(getNorm(y)) {
    void(0);
  }

  template <typename T>
  explicit operator T () const {
    return x;
  }

  ModInt operator-() const {
    return x == 0 ? 0 : mod - x;
  }

  ModInt& operator+=(const ModInt& ot) {
    if ((x += ot.x) >= mod) {
      x -= mod;
    }
    return *this;
  }

  friend ModInt operator+(const ModInt& a, const ModInt& b) {
    ModInt res = a;
    return res += b;
  }

  ModInt& operator-=(const ModInt& ot) {
    if ((x -= ot.x) < 0) {
      x += mod;
    }
    return *this;
  }

  friend ModInt operator-(const ModInt& a, const ModInt& b) {
    ModInt res = a;
    return res -= b;
  }

  ModInt& operator*=(const ModInt& ot) {
    x = int(1LL * x * ot.x % mod);
    return *this;
  }

  friend ModInt operator*(const ModInt& a, const ModInt& b) {
    ModInt res = a;
    return res *= b;
  }

  ModInt& operator/=(const ModInt& ot) {
    x = int(1LL * x * getInversed(ot.x) % mod);
    return *this;
  }

  friend ModInt operator/(const ModInt& a, const ModInt& b) {
    ModInt res = a;
    return res /= b;
  }

  friend bool operator==(const ModInt& a, const ModInt& b) {
    return int(a) == int(b);
  }

  friend bool operator!=(const ModInt& a, const ModInt& b) {
    return int(a) != int(b);
  }

  friend bool operator<(const ModInt& a, const ModInt& b) {
    return int(a) < int(b);
  }

  friend bool operator<=(const ModInt& a, const ModInt& b) {
    return int(a) <= int(b);
  }

  friend bool operator>(const ModInt& a, const ModInt& b) {
    return int(a) > int(b);
  }

  friend bool operator>=(const ModInt& a, const ModInt& b) {
    return int(a) >= int(b);
  }

  friend std::istream& operator>>(std::istream& stream, ModInt& x) {
    long long t;
    stream >> t;
    x = t;
    return stream;
  }

  friend std::ostream& operator<<(std::ostream& stream, const ModInt& x) {
    return stream << int(x);
  }
};

struct DynamicModInt {
  static int mod;
  int x;

  static int getNorm(long long x) {
    assert(mod > 0);
    if (x < -mod || mod <= x) {
      x %= mod;
    }
    if (x < 0) {
      x += mod;
    }
    return int(x);
  }

  static int getInversed(long long x) {
    x = getNorm(x);
    long long m = mod;
    long long u = 1;
    long long v = 0;
    while (m != 0) {
      int t = int(x / m);
      x -= t * m;
      u -= t * v;
      std::swap(x, m);
      std::swap(u, v);
    }
    assert(x == 1);
    return getNorm(u);
  }

  /* implicit */ DynamicModInt(long long y = 0) : x(getNorm(y)) {
    void(0);
  }

  template <typename T>
  explicit operator T() const {
    return x;
  }

  DynamicModInt operator-() const {
    return x == 0 ? 0 : mod - x;
  }

  DynamicModInt& operator+=(const DynamicModInt& ot) {
    if ((x += ot.x) >= mod) {
      x -= mod;
    }
    return *this;
  }

  friend DynamicModInt operator+(const DynamicModInt& a, const DynamicModInt& b) {
    DynamicModInt res = a;
    return res += b;
  }

  DynamicModInt& operator-=(const DynamicModInt& ot) {
    if ((x -= ot.x) < 0) {
      x += mod;
    }
    return *this;
  }

  friend DynamicModInt operator-(const DynamicModInt& a, const DynamicModInt& b) {
    DynamicModInt res = a;
    return res -= b;
  }

  DynamicModInt& operator*=(const DynamicModInt& ot) {
    x = int(1LL * x * ot.x % mod);
    return *this;
  }

  friend DynamicModInt operator*(const DynamicModInt& a, const DynamicModInt& b) {
    DynamicModInt res = a;
    return res *= b;
  }

  DynamicModInt& operator/=(const DynamicModInt& ot) {
    x = int(1LL * x * getInversed(ot.x) % mod);
    return *this;
  }

  friend DynamicModInt operator/(const DynamicModInt& a, const DynamicModInt& b) {
    DynamicModInt res = a;
    return res /= b;
  }

  friend bool operator==(const DynamicModInt& a, const DynamicModInt& b) {
    return int(a) == int(b);
  }

  friend bool operator!=(const DynamicModInt& a, const DynamicModInt& b) {
    return int(a) != int(b);
  }

  friend bool operator<(const DynamicModInt& a, const DynamicModInt& b) {
    return int(a) < int(b);
  }

  friend bool operator<=(const DynamicModInt& a, const DynamicModInt& b) {
    return int(a) <= int(b);
  }

  friend bool operator>(const DynamicModInt& a, const DynamicModInt& b) {
    return int(a) > int(b);
  }

  friend bool operator>=(const DynamicModInt& a, const DynamicModInt& b) {
    return int(a) >= int(b);
  }

  friend std::istream& operator>>(std::istream& stream, DynamicModInt& x) {
    long long t;
    stream >> t;
    x = t;
    return stream;
  }

  friend std::ostream& operator<<(std::ostream& stream, const DynamicModInt& x) {
    return stream << int(x);
  }
};

constexpr int mod = static_cast<int>(1E9) + 7;

using Z = ModInt<mod>;