#include <bits/stdc++.h>
#pragma GCC target("avx2,avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
using ll = long long;
using ull = unsigned long long;
using i128 = __int128_t;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
constexpr char ln = '\n';
istream& operator>>(istream& is, __int128_t& x) {
  x = 0;
  string s;
  is >> s;
  int n = int(s.size()), it = 0;
  if (s[0] == '-') it++;
  for (; it < n; it++) x = (x * 10 + s[it] - '0');
  if (s[0] == '-') x = -x;
  return is;
}
ostream& operator<<(ostream& os, __int128_t x) {
  if (x == 0) return os << 0;
  if (x < 0) os << '-', x = -x;
  deque<int> deq;
  while (x) deq.emplace_front(x % 10), x /= 10;
  for (int e : deq) os << e;
  return os;
}
template <class T1, class T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
  return os << "(" << p.first << ", " << p.second << ")";
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  os << "{";
  for (int i = 0; i < int(v.size()); i++) {
    if (i) os << ", ";
    os << v[i];
  }
  return os << "}";
}
template <class Container>
inline int SZ(Container& v) {
  return int(v.size());
}
template <class T>
inline void UNIQUE(vector<T>& v) {
  v.erase(unique(v.begin(), v.end()), v.end());
}
template <class T1, class T2>
inline bool chmax(T1& a, T2 b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T1, class T2>
inline bool chmin(T1& a, T2 b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
inline int topbit(int x) { return x == 0 ? -1 : 31 - __builtin_clz(x); }
inline int topbit(long long x) { return x == 0 ? -1 : 63 - __builtin_clzll(x); }
inline int botbit(int x) { return x == 0 ? 32 : __builtin_ctz(x); }
inline int botbit(long long x) { return x == 0 ? 64 : __builtin_ctzll(x); }
inline int popcount(int x) { return __builtin_popcount(x); }
inline int popcount(long long x) { return __builtin_popcountll(x); }
inline int kthbit(long long x, int k) { return (x >> k) & 1; }
inline constexpr long long TEN(int x) { return x == 0 ? 1 : TEN(x - 1) * 10; }
inline void print() { cout << "\n"; }
template <class T>
inline void print(const vector<T>& v) {
  for (int i = 0; i < int(v.size()); i++) {
    if (i) cout << " ";
    cout << v[i];
  }
  print();
}
template <class T, class... Args>
inline void print(const T& x, const Args&... args) {
  cout << x << " ";
  print(args...);
}
struct fast_ios {
  fast_ios() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
  };
} fast_ios_;
template <int m>
struct ModInt {
 public:
  static constexpr int mod() { return m; }
  static ModInt raw(int v) {
    ModInt x;
    x._v = v;
    return x;
  }
  ModInt() : _v(0) {}
  ModInt(long long v) {
    long long x = (long long)(v % (long long)(umod()));
    if (x < 0) x += umod();
    _v = (unsigned int)(x);
  }
  unsigned int val() const { return _v; }
  ModInt& operator++() {
    _v++;
    if (_v == umod()) _v = 0;
    return *this;
  }
  ModInt& operator--() {
    if (_v == 0) _v = umod();
    _v--;
    return *this;
  }
  ModInt operator++(int) {
    ModInt result = *this;
    ++*this;
    return result;
  }
  ModInt operator--(int) {
    ModInt result = *this;
    --*this;
    return result;
  }
  ModInt& operator+=(const ModInt& rhs) {
    _v += rhs._v;
    if (_v >= umod()) _v -= umod();
    return *this;
  }
  ModInt& operator-=(const ModInt& rhs) {
    _v -= rhs._v;
    if (_v >= umod()) _v += umod();
    return *this;
  }
  ModInt& operator*=(const ModInt& rhs) {
    unsigned long long z = _v;
    z *= rhs._v;
    _v = (unsigned int)(z % umod());
    return *this;
  }
  ModInt& operator^=(long long n) {
    ModInt x = *this;
    *this = 1;
    if (n < 0) x = x.inv(), n = -n;
    while (n) {
      if (n & 1) *this *= x;
      x *= x;
      n >>= 1;
    }
    return *this;
  }
  ModInt& operator/=(const ModInt& rhs) { return *this = *this * rhs.inv(); }
  ModInt operator+() const { return *this; }
  ModInt operator-() const { return ModInt() - *this; }
  ModInt pow(long long n) const {
    ModInt r = *this;
    r ^= n;
    return r;
  }
  ModInt inv() const {
    int a = _v, b = umod(), y = 1, z = 0, t;
    for (;;) {
      t = a / b;
      a -= t * b;
      if (a == 0) {
        assert(b == 1 || b == -1);
        return ModInt(b * z);
      }
      y -= t * z;
      t = b / a;
      b -= t * a;
      if (b == 0) {
        assert(a == 1 || a == -1);
        return ModInt(a * y);
      }
      z -= t * y;
    }
  }
  friend ModInt operator+(const ModInt& lhs, const ModInt& rhs) {
    return ModInt(lhs) += rhs;
  }
  friend ModInt operator-(const ModInt& lhs, const ModInt& rhs) {
    return ModInt(lhs) -= rhs;
  }
  friend ModInt operator*(const ModInt& lhs, const ModInt& rhs) {
    return ModInt(lhs) *= rhs;
  }
  friend ModInt operator/(const ModInt& lhs, const ModInt& rhs) {
    return ModInt(lhs) /= rhs;
  }
  friend ModInt operator^(const ModInt& lhs, long long rhs) {
    return ModInt(lhs) ^= rhs;
  }
  friend bool operator==(const ModInt& lhs, const ModInt& rhs) {
    return lhs._v == rhs._v;
  }
  friend bool operator!=(const ModInt& lhs, const ModInt& rhs) {
    return lhs._v != rhs._v;
  }
  friend ModInt operator+(long long lhs, const ModInt& rhs) {
    return (ModInt(lhs) += rhs);
  }
  friend ModInt operator-(long long lhs, const ModInt& rhs) {
    return (ModInt(lhs) -= rhs);
  }
  friend ModInt operator*(long long lhs, const ModInt& rhs) {
    return (ModInt(lhs) *= rhs);
  }
  friend ostream& operator<<(ostream& os, const ModInt& rhs) {
    return os << rhs._v;
  }

 private:
  unsigned int _v;
  static constexpr unsigned int umod() { return m; }
};
constexpr int MOD = 1000000007;
using mint = ModInt<MOD>;
struct ModCombination {
  vector<mint> Fac, Facinv;
  ModCombination(int x) {
    Fac.resize(x + 1);
    Facinv.resize(x + 1);
    Fac[0] = 1;
    for (int i = 0; i < x; ++i) Fac[i + 1] = Fac[i] * (i + 1);
    Facinv[x] = Fac[0] / Fac[x];
    for (int i = x; i > 0; --i) Facinv[i - 1] = Facinv[i] * i;
  }
  mint get(int n, int k) {
    if (k < 0 || k > n) return 0;
    return Fac[n] * Facinv[k] * Facinv[n - k];
  }
};
int main() {
  int N;
  cin >> N;
  ModCombination MC(100000);
  vector<vector<mint>> dp(N + 1, vector<mint>(N + 1));
  dp[0][0] = 1;
  for (int i = 0; i < (N); i++) {
    for (int j = 0; j < (N + 1); j++) {
      dp[i + 1][j] += dp[i][j] * j;
      if (j < N) dp[i + 1][j + 1] += dp[i][j];
    }
  }
  mint ans = 0;
  for (int i = 0; i < (N); i++)
    for (int j = 0; j < (i + 1); j++) ans += dp[i][j] * MC.get(N, i);
  cout << ans << ln;
}

### Prompt

Please provide a Cpp coded solution to the problem described below:

Little Johnny has recently learned about set theory. Now he is studying binary relations. You've probably heard the term "equivalence relation". These relations are very important in many areas of mathematics. For example, the equality of the two numbers is an equivalence relation.

A set ρ of pairs (a, b) of elements of some set A is called a binary relation on set A. For two elements a and b of the set A we say that they are in relation ρ, if pair <image>, in this case we use a notation <image>.

Binary relation is equivalence relation, if:

  1. It is reflexive (for any a it is true that <image>);
  2. It is symmetric (for any a, b it is true that if <image>, then <image>);
  3. It is transitive (if <image> and <image>, than <image>).



Little Johnny is not completely a fool and he noticed that the first condition is not necessary! Here is his "proof":

Take any two elements, a and b. If <image>, then <image> (according to property (2)), which means <image> (according to property (3)).

It's very simple, isn't it? However, you noticed that Johnny's "proof" is wrong, and decided to show him a lot of examples that prove him wrong.

Here's your task: count the number of binary relations over a set of size n such that they are symmetric, transitive, but not an equivalence relations (i.e. they are not reflexive).

Since their number may be very large (not 0, according to Little Johnny), print the remainder of integer division of this number by 109 + 7.

Input

A single line contains a single integer n (1 ≤ n ≤ 4000).

Output

In a single line print the answer to the problem modulo 109 + 7.

Examples

Input

1


Output

1


Input

2


Output

3


Input

3


Output

10

Note

If n = 1 there is only one such relation — an empty one, i.e. <image>. In other words, for a single element x of set A the following is hold: <image>.

If n = 2 there are three such relations. Let's assume that set A consists of two elements, x and y. Then the valid relations are <image>, ρ = {(x, x)}, ρ = {(y, y)}. It is easy to see that the three listed binary relations are symmetric and transitive relations, but they are not equivalence relations.

### Response

```cpp
#include <bits/stdc++.h>
#pragma GCC target("avx2,avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
using ll = long long;
using ull = unsigned long long;
using i128 = __int128_t;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
constexpr char ln = '\n';
istream& operator>>(istream& is, __int128_t& x) {
  x = 0;
  string s;
  is >> s;
  int n = int(s.size()), it = 0;
  if (s[0] == '-') it++;
  for (; it < n; it++) x = (x * 10 + s[it] - '0');
  if (s[0] == '-') x = -x;
  return is;
}
ostream& operator<<(ostream& os, __int128_t x) {
  if (x == 0) return os << 0;
  if (x < 0) os << '-', x = -x;
  deque<int> deq;
  while (x) deq.emplace_front(x % 10), x /= 10;
  for (int e : deq) os << e;
  return os;
}
template <class T1, class T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
  return os << "(" << p.first << ", " << p.second << ")";
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  os << "{";
  for (int i = 0; i < int(v.size()); i++) {
    if (i) os << ", ";
    os << v[i];
  }
  return os << "}";
}
template <class Container>
inline int SZ(Container& v) {
  return int(v.size());
}
template <class T>
inline void UNIQUE(vector<T>& v) {
  v.erase(unique(v.begin(), v.end()), v.end());
}
template <class T1, class T2>
inline bool chmax(T1& a, T2 b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T1, class T2>
inline bool chmin(T1& a, T2 b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
inline int topbit(int x) { return x == 0 ? -1 : 31 - __builtin_clz(x); }
inline int topbit(long long x) { return x == 0 ? -1 : 63 - __builtin_clzll(x); }
inline int botbit(int x) { return x == 0 ? 32 : __builtin_ctz(x); }
inline int botbit(long long x) { return x == 0 ? 64 : __builtin_ctzll(x); }
inline int popcount(int x) { return __builtin_popcount(x); }
inline int popcount(long long x) { return __builtin_popcountll(x); }
inline int kthbit(long long x, int k) { return (x >> k) & 1; }
inline constexpr long long TEN(int x) { return x == 0 ? 1 : TEN(x - 1) * 10; }
inline void print() { cout << "\n"; }
template <class T>
inline void print(const vector<T>& v) {
  for (int i = 0; i < int(v.size()); i++) {
    if (i) cout << " ";
    cout << v[i];
  }
  print();
}
template <class T, class... Args>
inline void print(const T& x, const Args&... args) {
  cout << x << " ";
  print(args...);
}
struct fast_ios {
  fast_ios() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
  };
} fast_ios_;
template <int m>
struct ModInt {
 public:
  static constexpr int mod() { return m; }
  static ModInt raw(int v) {
    ModInt x;
    x._v = v;
    return x;
  }
  ModInt() : _v(0) {}
  ModInt(long long v) {
    long long x = (long long)(v % (long long)(umod()));
    if (x < 0) x += umod();
    _v = (unsigned int)(x);
  }
  unsigned int val() const { return _v; }
  ModInt& operator++() {
    _v++;
    if (_v == umod()) _v = 0;
    return *this;
  }
  ModInt& operator--() {
    if (_v == 0) _v = umod();
    _v--;
    return *this;
  }
  ModInt operator++(int) {
    ModInt result = *this;
    ++*this;
    return result;
  }
  ModInt operator--(int) {
    ModInt result = *this;
    --*this;
    return result;
  }
  ModInt& operator+=(const ModInt& rhs) {
    _v += rhs._v;
    if (_v >= umod()) _v -= umod();
    return *this;
  }
  ModInt& operator-=(const ModInt& rhs) {
    _v -= rhs._v;
    if (_v >= umod()) _v += umod();
    return *this;
  }
  ModInt& operator*=(const ModInt& rhs) {
    unsigned long long z = _v;
    z *= rhs._v;
    _v = (unsigned int)(z % umod());
    return *this;
  }
  ModInt& operator^=(long long n) {
    ModInt x = *this;
    *this = 1;
    if (n < 0) x = x.inv(), n = -n;
    while (n) {
      if (n & 1) *this *= x;
      x *= x;
      n >>= 1;
    }
    return *this;
  }
  ModInt& operator/=(const ModInt& rhs) { return *this = *this * rhs.inv(); }
  ModInt operator+() const { return *this; }
  ModInt operator-() const { return ModInt() - *this; }
  ModInt pow(long long n) const {
    ModInt r = *this;
    r ^= n;
    return r;
  }
  ModInt inv() const {
    int a = _v, b = umod(), y = 1, z = 0, t;
    for (;;) {
      t = a / b;
      a -= t * b;
      if (a == 0) {
        assert(b == 1 || b == -1);
        return ModInt(b * z);
      }
      y -= t * z;
      t = b / a;
      b -= t * a;
      if (b == 0) {
        assert(a == 1 || a == -1);
        return ModInt(a * y);
      }
      z -= t * y;
    }
  }
  friend ModInt operator+(const ModInt& lhs, const ModInt& rhs) {
    return ModInt(lhs) += rhs;
  }
  friend ModInt operator-(const ModInt& lhs, const ModInt& rhs) {
    return ModInt(lhs) -= rhs;
  }
  friend ModInt operator*(const ModInt& lhs, const ModInt& rhs) {
    return ModInt(lhs) *= rhs;
  }
  friend ModInt operator/(const ModInt& lhs, const ModInt& rhs) {
    return ModInt(lhs) /= rhs;
  }
  friend ModInt operator^(const ModInt& lhs, long long rhs) {
    return ModInt(lhs) ^= rhs;
  }
  friend bool operator==(const ModInt& lhs, const ModInt& rhs) {
    return lhs._v == rhs._v;
  }
  friend bool operator!=(const ModInt& lhs, const ModInt& rhs) {
    return lhs._v != rhs._v;
  }
  friend ModInt operator+(long long lhs, const ModInt& rhs) {
    return (ModInt(lhs) += rhs);
  }
  friend ModInt operator-(long long lhs, const ModInt& rhs) {
    return (ModInt(lhs) -= rhs);
  }
  friend ModInt operator*(long long lhs, const ModInt& rhs) {
    return (ModInt(lhs) *= rhs);
  }
  friend ostream& operator<<(ostream& os, const ModInt& rhs) {
    return os << rhs._v;
  }

 private:
  unsigned int _v;
  static constexpr unsigned int umod() { return m; }
};
constexpr int MOD = 1000000007;
using mint = ModInt<MOD>;
struct ModCombination {
  vector<mint> Fac, Facinv;
  ModCombination(int x) {
    Fac.resize(x + 1);
    Facinv.resize(x + 1);
    Fac[0] = 1;
    for (int i = 0; i < x; ++i) Fac[i + 1] = Fac[i] * (i + 1);
    Facinv[x] = Fac[0] / Fac[x];
    for (int i = x; i > 0; --i) Facinv[i - 1] = Facinv[i] * i;
  }
  mint get(int n, int k) {
    if (k < 0 || k > n) return 0;
    return Fac[n] * Facinv[k] * Facinv[n - k];
  }
};
int main() {
  int N;
  cin >> N;
  ModCombination MC(100000);
  vector<vector<mint>> dp(N + 1, vector<mint>(N + 1));
  dp[0][0] = 1;
  for (int i = 0; i < (N); i++) {
    for (int j = 0; j < (N + 1); j++) {
      dp[i + 1][j] += dp[i][j] * j;
      if (j < N) dp[i + 1][j + 1] += dp[i][j];
    }
  }
  mint ans = 0;
  for (int i = 0; i < (N); i++)
    for (int j = 0; j < (i + 1); j++) ans += dp[i][j] * MC.get(N, i);
  cout << ans << ln;
}

```