#include <bits/stdc++.h>
using namespace std;
void rset();
void init_test();
void solve();
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed;
  cout.precision(20);
  init_test();
  return 0;
}
template <typename T>
void chmin(T& a, T b) {
  if (a > b) a = b;
}
template <typename T>
void chmax(T& a, T b) {
  if (a < b) a = b;
}
template <typename T>
void MACRO_rdv2_Init(int n, T& t) {
  t.resize(n);
}
template <typename First, typename... Rest>
void MACRO_rdv2_Init(int n, First& first, Rest&... rest) {
  first.resize(n);
  MACRO_rdv2_Init(n, rest...);
}
template <typename T>
void MACRO_rdv2_Scan(int p, T& t) {
  std::cin >> t[p];
}
template <typename First, typename... Rest>
void MACRO_rdv2_Scan(int p, First& first, Rest&... rest) {
  std::cin >> first[p];
  MACRO_rdv2_Scan(p, rest...);
}
template <typename T>
void wrv(const vector<T>& v) {
  for (int(__ii) = (0); (__ii) < (((int)v.size())); ++(__ii)) {
    if (__ii) cout << ' ';
    cout << v[__ii];
  }
  cout << '\n';
}
template <typename T>
void wrm(const vector<vector<T>>& v) {
  for (int(__ii) = (0); (__ii) < (((int)v.size())); ++(__ii)) {
    for (int(__jj) = (0); (__jj) < (v[__ii].size()); ++(__jj)) {
      if (__jj) cout << ' ';
      cout << v[__ii][__jj];
    }
    cout << '\n';
  }
}
template <typename T>
void sc(T& x) {
  cin >> x;
}
template <typename Head, typename... Tail>
void sc(Head& head, Tail&... tail) {
  cin >> head;
  sc(tail...);
}
template <typename T>
void wr(const T& x) {
  cout << x << '\n';
}
template <typename Head, typename... Tail>
void wr(const Head& head, const Tail&... tail) {
  cout << head << ' ';
  wr(tail...);
}
template <typename T>
void wrf(const T& x) {
  cout << x << endl;
}
template <typename Head, typename... Tail>
void wrf(const Head& head, const Tail&... tail) {
  cout << head << ' ';
  wrf(tail...);
}
template <typename T>
void debug_out(const T& x) {
  cerr << x << '\n';
}
template <typename Head, typename... Tail>
void debug_out(const Head& head, const Tail&... tail) {
  cerr << head << ' ';
  debug_out(tail...);
}
template <typename... T>
void err(const T&... cod) {
  wr(cod...);
  exit(0);
}
const int mod = 1e9 + 7;
void add_self(int& x, int y) {
  x += y;
  if (x >= mod) x -= mod;
}
void sub_self(int& x, int y) {
  x -= y;
  if (x < 0) x += mod;
}
int add(int x, int y) {
  x += y;
  if (x >= mod) x -= mod;
  return x;
}
int sub(int x, int y) {
  x -= y;
  if (x < 0) x += mod;
  return x;
}
int powmod(long long a, long long b) {
  long long res = 1;
  a %= mod;
  assert(b >= 0);
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
  }
  return res % mod;
}
int mult(int x, int y) { return (1LL * x * y) % mod; }
int inv(int x) { return powmod(x, mod - 2); }
int divide(int x, int y) { return mult(x, inv(y)); }
const int N = 2020;
int n;
int dp[N][N];
int f(int d, int bal) {
  if (dp[d][bal] != -1) return dp[d][bal];
  if (bal > 2 * n - d) return 0;
  if (d == 2 * n - 1) return 1;
  int ans = add(d % 2, f(d + 1, bal + 1));
  if (bal > 0) add_self(ans, f(d + 1, bal - 1));
  return dp[d][bal] = ans;
}
void solve() {
  cin >> n;
  memset(dp, -1, sizeof dp);
  wr(f(0, 0));
}
void init_test() {
  int qq = 1;
  while (qq--) solve();
}

### Prompt

Create a solution in Cpp for the following problem:

Neko is playing with his toys on the backyard of Aki's house. Aki decided to play a prank on him, by secretly putting catnip into Neko's toys. Unfortunately, he went overboard and put an entire bag of catnip into the toys...

It took Neko an entire day to turn back to normal. Neko reported to Aki that he saw a lot of weird things, including a [trie](https://en.wikipedia.org/wiki/Trie) of all correct bracket sequences of length 2n.

The definition of correct bracket sequence is as follows:

  * The empty sequence is a correct bracket sequence, 
  * If s is a correct bracket sequence, then (\,s ) is a correct bracket sequence, 
  * If s and t are a correct bracket sequence, then st is also a correct bracket sequence. 



For example, the strings "(())", "()()" form a correct bracket sequence, while ")(" and "((" not.

Aki then came up with an interesting problem: What is the size of the maximum matching (the largest set of edges such that there are no two edges with a common vertex) in this trie? Since the answer can be quite large, print it modulo 10^9 + 7.

Input

The only line contains a single integer n (1 ≤ n ≤ 1000).

Output

Print exactly one integer — the size of the maximum matching in the trie. Since the answer can be quite large, print it modulo 10^9 + 7.

Examples

Input


1


Output


1


Input


2


Output


3


Input


3


Output


9

Note

The pictures below illustrate tries in the first two examples (for clarity, the round brackets are replaced with angle brackets). The maximum matching is highlighted with blue.

<image> <image>

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
void rset();
void init_test();
void solve();
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed;
  cout.precision(20);
  init_test();
  return 0;
}
template <typename T>
void chmin(T& a, T b) {
  if (a > b) a = b;
}
template <typename T>
void chmax(T& a, T b) {
  if (a < b) a = b;
}
template <typename T>
void MACRO_rdv2_Init(int n, T& t) {
  t.resize(n);
}
template <typename First, typename... Rest>
void MACRO_rdv2_Init(int n, First& first, Rest&... rest) {
  first.resize(n);
  MACRO_rdv2_Init(n, rest...);
}
template <typename T>
void MACRO_rdv2_Scan(int p, T& t) {
  std::cin >> t[p];
}
template <typename First, typename... Rest>
void MACRO_rdv2_Scan(int p, First& first, Rest&... rest) {
  std::cin >> first[p];
  MACRO_rdv2_Scan(p, rest...);
}
template <typename T>
void wrv(const vector<T>& v) {
  for (int(__ii) = (0); (__ii) < (((int)v.size())); ++(__ii)) {
    if (__ii) cout << ' ';
    cout << v[__ii];
  }
  cout << '\n';
}
template <typename T>
void wrm(const vector<vector<T>>& v) {
  for (int(__ii) = (0); (__ii) < (((int)v.size())); ++(__ii)) {
    for (int(__jj) = (0); (__jj) < (v[__ii].size()); ++(__jj)) {
      if (__jj) cout << ' ';
      cout << v[__ii][__jj];
    }
    cout << '\n';
  }
}
template <typename T>
void sc(T& x) {
  cin >> x;
}
template <typename Head, typename... Tail>
void sc(Head& head, Tail&... tail) {
  cin >> head;
  sc(tail...);
}
template <typename T>
void wr(const T& x) {
  cout << x << '\n';
}
template <typename Head, typename... Tail>
void wr(const Head& head, const Tail&... tail) {
  cout << head << ' ';
  wr(tail...);
}
template <typename T>
void wrf(const T& x) {
  cout << x << endl;
}
template <typename Head, typename... Tail>
void wrf(const Head& head, const Tail&... tail) {
  cout << head << ' ';
  wrf(tail...);
}
template <typename T>
void debug_out(const T& x) {
  cerr << x << '\n';
}
template <typename Head, typename... Tail>
void debug_out(const Head& head, const Tail&... tail) {
  cerr << head << ' ';
  debug_out(tail...);
}
template <typename... T>
void err(const T&... cod) {
  wr(cod...);
  exit(0);
}
const int mod = 1e9 + 7;
void add_self(int& x, int y) {
  x += y;
  if (x >= mod) x -= mod;
}
void sub_self(int& x, int y) {
  x -= y;
  if (x < 0) x += mod;
}
int add(int x, int y) {
  x += y;
  if (x >= mod) x -= mod;
  return x;
}
int sub(int x, int y) {
  x -= y;
  if (x < 0) x += mod;
  return x;
}
int powmod(long long a, long long b) {
  long long res = 1;
  a %= mod;
  assert(b >= 0);
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
  }
  return res % mod;
}
int mult(int x, int y) { return (1LL * x * y) % mod; }
int inv(int x) { return powmod(x, mod - 2); }
int divide(int x, int y) { return mult(x, inv(y)); }
const int N = 2020;
int n;
int dp[N][N];
int f(int d, int bal) {
  if (dp[d][bal] != -1) return dp[d][bal];
  if (bal > 2 * n - d) return 0;
  if (d == 2 * n - 1) return 1;
  int ans = add(d % 2, f(d + 1, bal + 1));
  if (bal > 0) add_self(ans, f(d + 1, bal - 1));
  return dp[d][bal] = ans;
}
void solve() {
  cin >> n;
  memset(dp, -1, sizeof dp);
  wr(f(0, 0));
}
void init_test() {
  int qq = 1;
  while (qq--) solve();
}

```