#include<bits/stdc++.h>

#include <time.h>
using namespace std;
#define INFS (1LL<<28)
#define DEKAI 1000000007
//#define MOD 1000000007
#define lp(i,n) for(int i=0;i<n;i++)
#define lps(i,n) for(int i=1;i<=n;i++)
#define all(c) begin(c), end(c)

//#define int long long 

namespace {
	#define __DECLARE__(C)    \
	    template <typename T> \
	    std::ostream &operator<<(std::ostream &, const C<T> &);

	#define __DECLAREM__(C)               \
	    template <typename T, typename U> \
	    std::ostream &operator<<(std::ostream &, const C<T, U> &);

	__DECLARE__(std::vector)
	__DECLARE__(std::deque)
	__DECLARE__(std::set)
	__DECLARE__(std::stack)
	__DECLARE__(std::queue)
	__DECLARE__(std::priority_queue)
	__DECLARE__(std::unordered_set)
	__DECLAREM__(std::map)
	__DECLAREM__(std::unordered_map)

	template <typename T, typename U>
	std::ostream &operator<<(std::ostream &, const std::pair<T, U> &);
	template <typename... T>
	std::ostream &operator<<(std::ostream &, const std::tuple<T...> &);
	template <typename T, std::size_t N>
	std::ostream &operator<<(std::ostream &, const std::array<T, N> &);

	template <typename Tuple, std::size_t N>
	struct __TuplePrinter__ {
	    static void print(std::ostream &os, const Tuple &t) {
	        __TuplePrinter__<Tuple, N - 1>::print(os, t);
	        os << ", " << std::get<N - 1>(t);
	    }
	};

	template <typename Tuple>
	struct __TuplePrinter__<Tuple, 1> {
	    static void print(std::ostream &os, const Tuple &t) { os << std::get<0>(t); }
	};

	template <typename... T>
	std::ostream &operator<<(std::ostream &os, const std::tuple<T...> &t) {
	    os << '(';
	    __TuplePrinter__<decltype(t), sizeof...(T)>::print(os, t);
	    os << ')';
	    return os;
	}

	template <typename T, typename U>
	std::ostream &operator<<(std::ostream &os, const std::pair<T, U> &v) {
	    return os << '(' << v.first << ", " << v.second << ')';
	}

	#define __INNER__                             \
	    os << '[';                                \
	    for (auto it = begin(c); it != end(c);) { \
	        os << *it;                            \
	        os << (++it != end(c) ? ", " : "");   \
	    }                                         \
	    return os << ']';

	template <typename T, std::size_t N>
	std::ostream &operator<<(std::ostream &os, const std::array<T, N> &c) {
	    __INNER__
	}

	#define __DEFINE__(C)                                           \
	    template <typename T>                                       \
	    std::ostream &operator<<(std::ostream &os, const C<T> &c) { \
	        __INNER__                                               \
	    }

	#define __DEFINEM__(C)                                             \
	    template <typename T, typename U>                              \
	    std::ostream &operator<<(std::ostream &os, const C<T, U> &c) { \
	        __INNER__                                                  \
	    }

	#define __DEFINEW__(C, M1, M2)                                  \
	    template <typename T>                                       \
	    std::ostream &operator<<(std::ostream &os, const C<T> &c) { \
	        std::deque<T> v;                                        \
	        for (auto d = c; !d.empty(); d.pop()) v.M1(d.M2());     \
	        return os << v;                                         \
	    }

	__DEFINE__(std::vector)
	__DEFINE__(std::deque)
	__DEFINE__(std::set)
	__DEFINEW__(std::stack, push_front, top)
	__DEFINEW__(std::queue, push_back, front)
	__DEFINEW__(std::priority_queue, push_front, top)
	__DEFINE__(std::unordered_set)
	__DEFINEM__(std::map)
	__DEFINEM__(std::unordered_map)
}

#define pii pair<int,int>
#define ll long long
inline ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
inline ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

// modint 

//#define int long long
#define double long double 
#define rep(i,j,k)for(int i=j;i<k;i++)

long long myPow(long long x, long long n, long long m){
  if(n == 0)
    return 1;
  if(n % 2 == 0)
    return myPow(x * x % m, n / 2, m);
  else
    return x * myPow(x, n - 1, m) % m;
}
const ll mod = 1000000007;

template< int mod >
struct ModInt {
  int x;

  ModInt() : x(0) {}

  ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}

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

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

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

  ModInt &operator/=(const ModInt &p) {
    *this *= p.inverse();
    return *this;
  }

  ModInt operator-() const { return ModInt(-x); }

  ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }

  ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }

  ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }

  ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }

  bool operator==(const ModInt &p) const { return x == p.x; }

  bool operator!=(const ModInt &p) const { return x != p.x; }

  ModInt inverse() const {
    int a = x, b = mod, u = 1, v = 0, t;
    while(b > 0) {
      t = a / b;
      swap(a -= t * b, b);
      swap(u -= t * v, v);
    }
    return ModInt(u);
  }

  ModInt pow(int64_t n) const {
    ModInt ret(1), mul(x);
    while(n > 0) {
      if(n & 1) ret *= mul;
      mul *= mul;
      n >>= 1;
    }
    return ret;
  }

  friend ostream &operator<<(ostream &os, const ModInt &p) {
    return os << p.x;
  }

  friend istream &operator>>(istream &is, ModInt &a) {
    int64_t t;
    is >> t;
    a = ModInt< mod >(t);
    return (is);
  }

  static int get_mod() { return mod; }
};

using modint = ModInt< mod >;

template< typename T >
struct Combination {
  vector< T > _fact, _rfact, _inv;

  Combination(int sz) : _fact(sz + 1), _rfact(sz + 1), _inv(sz + 1) {
    _fact[0] = _rfact[sz] = _inv[0] = 1;
    for(int i = 1; i <= sz; i++) _fact[i] = _fact[i - 1] * i;
    _rfact[sz] /= _fact[sz];
    for(int i = sz - 1; i >= 0; i--) _rfact[i] = _rfact[i + 1] * (i + 1);
    for(int i = 1; i <= sz; i++) _inv[i] = _rfact[i] * _fact[i - 1];
  }

  inline T fact(int k) const { return _fact[k]; }

  inline T rfact(int k) const { return _rfact[k]; }

  inline T inv(int k) const { return _inv[k]; }

  T P(int n, int r) const {
    if(r < 0 || n < r) return 0;
    return fact(n) * rfact(n - r);
  }

  T C(int p, int q) const {
    if(q < 0 || p < q) return 0;
    return fact(p) * rfact(q) * rfact(p - q);
  }

  T H(int n, int r) const {
    if(n < 0 || r < 0) return (0);
    return r == 0 ? 1 : C(n + r - 1, r);
  }
};
namespace FastFourierTransform {
  using real = double;

  struct C {
    real x, y;

    C() : x(0), y(0) {}

    C(real x, real y) : x(x), y(y) {}

    inline C operator+(const C &c) const { return C(x + c.x, y + c.y); }

    inline C operator-(const C &c) const { return C(x - c.x, y - c.y); }

    inline C operator*(const C &c) const { return C(x * c.x - y * c.y, x * c.y + y * c.x); }

    inline C conj() const { return C(x, -y); }
  };

  const real PI = acosl(-1);
  int base = 1;
  vector< C > rts = { {0, 0},
                     {1, 0} };
  vector< int > rev = {0, 1};


  void ensure_base(int nbase) {
    if(nbase <= base) return;
    rev.resize(1 << nbase);
    rts.resize(1 << nbase);
    for(int i = 0; i < (1 << nbase); i++) {
      rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << (nbase - 1));
    }
    while(base < nbase) {
      real angle = PI * 2.0 / (1 << (base + 1));
      for(int i = 1 << (base - 1); i < (1 << base); i++) {
        rts[i << 1] = rts[i];
        real angle_i = angle * (2 * i + 1 - (1 << base));
        rts[(i << 1) + 1] = C(cos(angle_i), sin(angle_i));
      }
      ++base;
    }
  }

  void fft(vector< C > &a, int n) {
    assert((n & (n - 1)) == 0);
    int zeros = __builtin_ctz(n);
    ensure_base(zeros);
    int shift = base - zeros;
    for(int i = 0; i < n; i++) {
      if(i < (rev[i] >> shift)) {
        swap(a[i], a[rev[i] >> shift]);
      }
    }
    for(int k = 1; k < n; k <<= 1) {
      for(int i = 0; i < n; i += 2 * k) {
        for(int j = 0; j < k; j++) {
          C z = a[i + j + k] * rts[j + k];
          a[i + j + k] = a[i + j] - z;
          a[i + j] = a[i + j] + z;
        }
      }
    }
  }

  vector< int64_t > multiply(const vector< int > &a, const vector< int > &b) {
    int need = (int) a.size() + (int) b.size() - 1;
    int nbase = 1;
    while((1 << nbase) < need) nbase++;
    ensure_base(nbase);
    int sz = 1 << nbase;
    vector< C > fa(sz);
    for(int i = 0; i < sz; i++) {
      int x = (i < (int) a.size() ? a[i] : 0);
      int y = (i < (int) b.size() ? b[i] : 0);
      fa[i] = C(x, y);
    }
    fft(fa, sz);
    C r(0, -0.25 / (sz >> 1)), s(0, 1), t(0.5, 0);
    for(int i = 0; i <= (sz >> 1); i++) {
      int j = (sz - i) & (sz - 1);
      C z = (fa[j] * fa[j] - (fa[i] * fa[i]).conj()) * r;
      fa[j] = (fa[i] * fa[i] - (fa[j] * fa[j]).conj()) * r;
      fa[i] = z;
    }
    for(int i = 0; i < (sz >> 1); i++) {
      C A0 = (fa[i] + fa[i + (sz >> 1)]) * t;
      C A1 = (fa[i] - fa[i + (sz >> 1)]) * t * rts[(sz >> 1) + i];
      fa[i] = A0 + A1 * s;
    }
    fft(fa, sz >> 1);
    vector< int64_t > ret(need);
    for(int i = 0; i < need; i++) {
      ret[i] = llround(i & 1 ? fa[i >> 1].y : fa[i >> 1].x);
    }
    return ret;
  }
};
template< typename T >
struct ArbitraryModConvolution {
  using real = FastFourierTransform::real;
  using C = FastFourierTransform::C;

  ArbitraryModConvolution() = default;

  vector< T > multiply(const vector< T > &a, const vector< T > &b, int need = -1) {
    if(need == -1) need = a.size() + b.size() - 1;
    int nbase = 0;
    while((1 << nbase) < need) nbase++;
    FastFourierTransform::ensure_base(nbase);
    int sz = 1 << nbase;
    vector< C > fa(sz);
    for(int i = 0; i < a.size(); i++) {
      fa[i] = C(a[i].x & ((1 << 15) - 1), a[i].x >> 15);
    }
    fft(fa, sz);
    vector< C > fb(sz);
    if(a == b) {
      fb = fa;
    } else {
      for(int i = 0; i < b.size(); i++) {
        fb[i] = C(b[i].x & ((1 << 15) - 1), b[i].x >> 15);
      }
      fft(fb, sz);
    }
    real ratio = 0.25 / sz;
    C r2(0, -1), r3(ratio, 0), r4(0, -ratio), r5(0, 1);
    for(int i = 0; i <= (sz >> 1); i++) {
      int j = (sz - i) & (sz - 1);
      C a1 = (fa[i] + fa[j].conj());
      C a2 = (fa[i] - fa[j].conj()) * r2;
      C b1 = (fb[i] + fb[j].conj()) * r3;
      C b2 = (fb[i] - fb[j].conj()) * r4;
      if(i != j) {
        C c1 = (fa[j] + fa[i].conj());
        C c2 = (fa[j] - fa[i].conj()) * r2;
        C d1 = (fb[j] + fb[i].conj()) * r3;
        C d2 = (fb[j] - fb[i].conj()) * r4;
        fa[i] = c1 * d1 + c2 * d2 * r5;
        fb[i] = c1 * d2 + c2 * d1;
      }
      fa[j] = a1 * b1 + a2 * b2 * r5;
      fb[j] = a1 * b2 + a2 * b1;
    }
    fft(fa, sz);
    fft(fb, sz);
    vector< T > ret(need);
    for(int i = 0; i < need; i++) {
      int64_t aa = llround(fa[i].x);
      int64_t bb = llround(fb[i].x);
      int64_t cc = llround(fa[i].y);
      aa = T(aa).x, bb = T(bb).x, cc = T(cc).x;
      ret[i] = aa + (bb << 15) + (cc << 30);
    }
    return ret;
  }
};

template< typename T >
struct ArbitraryModConvolutionLong {
  using real = FastFourierTransform::real;
  using C = FastFourierTransform::C;
 
  ArbitraryModConvolutionLong() = default;
 
  vector< T > multiply(const vector< T > &a, const vector< T > &b, int need = -1) {
    if(need == -1) need = a.size() + b.size() - 1;
    int nbase = 0;
    while((1 << nbase) < need) nbase++;
    FastFourierTransform::ensure_base(nbase);
    int sz = 1 << nbase;
    vector< C > fa(sz);
    for(int i = 0; i < a.size(); i++) {
      fa[i] = C(a[i].x & ((1 << 19) - 1), a[i].x >> 19);
    }
    fft(fa, sz);
    vector< C > fb(sz);
    if(a == b) {
      fb = fa;
    } else {
      for(int i = 0; i < b.size(); i++) {
        fb[i] = C(b[i].x & ((1 << 19) - 1), b[i].x >> 19);
      }
      fft(fb, sz);
    }
    real ratio = 0.25 / sz;
    C r2(0, -1), r3(ratio, 0), r4(0, -ratio), r5(0, 1);
    for(int i = 0; i <= (sz >> 1); i++) {
      int j = (sz - i) & (sz - 1);
      C a1 = (fa[i] + fa[j].conj());
      C a2 = (fa[i] - fa[j].conj()) * r2;
      C b1 = (fb[i] + fb[j].conj()) * r3;
      C b2 = (fb[i] - fb[j].conj()) * r4;
      if(i != j) {
        C c1 = (fa[j] + fa[i].conj());
        C c2 = (fa[j] - fa[i].conj()) * r2;
        C d1 = (fb[j] + fb[i].conj()) * r3;
        C d2 = (fb[j] - fb[i].conj()) * r4;
        fa[i] = c1 * d1 + c2 * d2 * r5;
        fb[i] = c1 * d2 + c2 * d1;
      }
      fa[j] = a1 * b1 + a2 * b2 * r5;
      fb[j] = a1 * b2 + a2 * b1;
    }
    fft(fa, sz);
    fft(fb, sz);
    vector< T > ret(need);
    auto mul1 = T(2).pow(19);
    auto mul2 = T(2).pow(38);
    for(int i = 0; i < need; i++) {
      int64_t aa = llround(fa[i].x);
      int64_t bb = llround(fb[i].x);
      int64_t cc = llround(fa[i].y);
      aa = T(aa).x, bb = T(bb).x, cc = T(cc).x;
      ret[i] = (mul1 * bb) + (mul2 * cc) + aa;
    }
    return ret;
  }
};
template< typename T >
struct FormalPowerSeries : vector< T > {
  using vector< T >::vector;
  using P = FormalPowerSeries;

  using MULT = function< P(P, P) >;

  static MULT &get_mult() {
    static MULT mult = nullptr;
    return mult;
  }

  static void set_fft(MULT f) {
    get_mult() = f;
  }

  void shrink() {
    while(this->size() && this->back() == T(0)) this->pop_back();
  }

  P operator+(const P &r) const { return P(*this) += r; }

  P operator+(const T &v) const { return P(*this) += v; }

  P operator-(const P &r) const { return P(*this) -= r; }

  P operator-(const T &v) const { return P(*this) -= v; }

  P operator*(const P &r) const { return P(*this) *= r; }

  P operator*(const T &v) const { return P(*this) *= v; }

  P operator/(const P &r) const { return P(*this) /= r; }

  P operator%(const P &r) const { return P(*this) %= r; }

  P &operator+=(const P &r) {
    if(r.size() > this->size()) this->resize(r.size());
    for(int i = 0; i < r.size(); i++) (*this)[i] += r[i];
    return *this;
  }

  P &operator+=(const T &r) {
    if(this->empty()) this->resize(1);
    (*this)[0] += r;
    return *this;
  }

  P &operator-=(const P &r) {
    if(r.size() > this->size()) this->resize(r.size());
    for(int i = 0; i < r.size(); i++) (*this)[i] -= r[i];
    shrink();
    return *this;
  }

  P &operator-=(const T &r) {
    if(this->empty()) this->resize(1);
    (*this)[0] -= r;
    shrink();
    return *this;
  }

  P &operator*=(const T &v) {
    const int n = (int) this->size();
    for(int k = 0; k < n; k++) (*this)[k] *= v;
    return *this;
  }

  P &operator*=(const P &r) {
    if(this->empty() || r.empty()) {
      this->clear();
      return *this;
    }
    assert(get_mult() != nullptr);
    return *this = get_mult()(*this, r);
  }

  P &operator%=(const P &r) {
    return *this -= *this / r * r;
  }

  P operator-() const {
    P ret(this->size());
    for(int i = 0; i < this->size(); i++) ret[i] = -(*this)[i];
    return ret;
  }

  P &operator/=(const P &r) {
    if(this->size() < r.size()) {
      this->clear();
      return *this;
    }
    int n = this->size() - r.size() + 1;
    return *this = (rev().pre(n) * r.rev().inv(n)).pre(n).rev(n);
  }

  P pre(int sz) const {
    return P(begin(*this), begin(*this) + min((int) this->size(), sz));
  }

  P operator>>(int sz) const {
    if(this->size() <= sz) return {};
    P ret(*this);
    ret.erase(ret.begin(), ret.begin() + sz);
    return ret;
  }

  P operator<<(int sz) const {
    P ret(*this);
    ret.insert(ret.begin(), sz, T(0));
    return ret;
  }

  P rev(int deg = -1) const {
    P ret(*this);
    if(deg != -1) ret.resize(deg, T(0));
    reverse(begin(ret), end(ret));
    return ret;
  }

  P diff() const {
    const int n = (int) this->size();
    P ret(max(0, n - 1));
    for(int i = 1; i < n; i++) ret[i - 1] = (*this)[i] * T(i);
    return ret;
  }

  P integral() const {
    const int n = (int) this->size();
    P ret(n + 1);
    ret[0] = T(0);
    for(int i = 0; i < n; i++) ret[i + 1] = (*this)[i] / T(i + 1);
    return ret;
  }

  // F(0) must not be 0
  P inv(int deg = -1) const {
    assert(((*this)[0]) != T(0));
    const int n = (int) this->size();
    if(deg == -1) deg = n;
    P ret({T(1) / (*this)[0]});
    for(int i = 1; i < deg; i <<= 1) {
      ret = (ret + ret - ret * ret * pre(i << 1)).pre(i << 1);
    }
    return ret.pre(deg);
  }

  // F(0) must be 1
  P log(int deg = -1) const {
    assert((*this)[0] == 1);
    const int n = (int) this->size();
    if(deg == -1) deg = n;
    return (this->diff() * this->inv(deg)).pre(deg - 1).integral();
  }

  P sqrt(int deg = -1) const {
    const int n = (int) this->size();
    if(deg == -1) deg = n;

    if((*this)[0] == T(0)) {
      for(int i = 1; i < n; i++) {
        if((*this)[i] != T(0)) {
          if(i & 1) return {};
          if(deg - i / 2 <= 0) break;
          auto ret = (*this >> i).sqrt(deg - i / 2) << (i / 2);
          if(ret.size() < deg) ret.resize(deg, T(0));
          return ret;
        }
      }
      return P(deg, 0);
    }

    P ret({T(1)});
    T inv2 = T(1) / T(2);
    for(int i = 1; i < deg; i <<= 1) {
      ret = (ret + pre(i << 1) * ret.inv(i << 1)) * inv2;
    }
    return ret.pre(deg);
  }

  // F(0) must be 0
  P exp(int deg = -1) const {
    assert((*this)[0] == T(0));
    const int n = (int) this->size();
    if(deg == -1) deg = n;
    P ret({T(1)});
    for(int i = 1; i < deg; i <<= 1) {
      ret = (ret * (pre(i << 1) + T(1) - ret.log(i << 1))).pre(i << 1);
    }
    return ret.pre(deg);
  }

  P pow(int64_t k, int deg = -1) const {
    const int n = (int) this->size();
    if(deg == -1) deg = n;
    for(int i = 0; i < n; i++) {
      if((*this)[i] != T(0)) {
        T rev = T(1) / (*this)[i];
        P C(*this * rev);
        P D(n - i);
        for(int j = i; j < n; j++) D[j - i] = C[j];
        D = (D.log() * k).exp() * (*this)[i].pow(k);
        P E(deg);
        if(i * k > deg) return E;
        auto S = i * k;
        for(int j = 0; j + S < deg && j < D.size(); j++) E[j + S] = D[j];
        return E;
      }
    }
    return *this;
  }


  T eval(T x) const {
    T r = 0, w = 1;
    for(auto &v : *this) {
      r += w * v;
      w *= x;
    }
    return r;
  }
};
template< typename T >
T factorial(int64_t n) {
  if(n >= T::get_mod()) return 0;
  if(n == 0) return 1;

  const int64_t sn = sqrt(n);
  const T sn_inv = T(1) / sn;

  Combination< modint > comb(sn);
  using P = vector< T >;

  ArbitraryModConvolution< T > fft;
  using FPS = FormalPowerSeries< T >;
  auto mult = [&](const typename FPS::P &a, const typename FPS::P &b) {
    auto ret = fft.multiply(a, b);
    return typename FPS::P(ret.begin(), ret.end());
  };
  FPS::set_fft(mult);


  auto shift = [&](const P &f, T dx) {
    int n = (int) f.size();
    T a = dx * sn_inv;
    auto p1 = P(f);
    for(int i = 0; i < n; i++) {
      T d = comb.rfact(i) * comb.rfact((n - 1) - i);
      if(((n - 1 - i) & 1)) d = -d;
      p1[i] *= d;
    }
    auto p2 = P(2 * n);
    for(int i = 0; i < p2.size(); i++) {
      p2[i] = (a.x + i - n) <= 0 ? 1 : a + i - n;
    }
    for(int i = 1; i < p2.size(); i++) {
      p2[i] *= p2[i - 1];
    }
    T prod = p2[2 * n - 1];
    T prod_inv = T(1) / prod;
    for(int i = 2 * n - 1; i > 0; --i) {
      p2[i] = prod_inv * p2[i - 1];
      prod_inv *= a + i - n;
    }
    p2[0] = prod_inv;
    auto p3 = fft.multiply(p1, p2, (int) p2.size());
    p1 = P(p3.begin() + p1.size(), p3.begin() + p2.size());
    prod = 1;
    for(int i = 0; i < n; i++) {
      prod *= a + n - 1 - i;
    }
    for(int i = n - 1; i >= 0; --i) {
      p1[i] *= prod;
      prod *= p2[n + i] * (a + i - n);
    }
    return p1;
  };
  function< P(int) > rec = [&](int64_t n) {
    if(n == 1) return P({1, 1 + sn});
    int64_t nh = n >> 1;
    auto a1 = rec(nh);
    auto a2 = shift(a1, nh);
    auto b1 = shift(a1, sn * nh);
    auto b2 = shift(a1, sn * nh + nh);
    for(int i = 0; i <= nh; i++) a1[i] *= a2[i];
    for(int i = 1; i <= nh; i++) a1.emplace_back(b1[i] * b2[i]);
    if(n & 1) {
      for(int64_t i = 0; i < n; i++) {
        a1[i] *= n + 1LL * sn * i;
      }
      T prod = 1;
      for(int64_t i = 1LL * n * sn; i < 1LL * n * sn + n; i++) {
        prod *= (i + 1);
      }
      a1.push_back(prod);
    }
    return a1;
  };
  auto vs = rec(sn);
  T ret = 1;
  for(int64_t i = 0; i < sn; i++) ret *= vs[i];
  for(int64_t i = 1LL * sn * sn + 1; i <= n; i++) ret *= i;
  return ret;
}


modint C(int n,int k){
	modint ue= factorial< modint >(n);
	modint sita=factorial<modint>(k);
	sita*=factorial<modint>(n-k);
	return ue/sita;
}

signed main(){
	int n;
	cin>>n;
	int a,b;
	cin>>a>>b;
	modint ans=myPow(2,n,DEKAI)-1;
	ans-=C(n,a);
	ans-=C(n,b);
	cout<<ans<<endl;
} 

Measured memory_bytes: 4368