#include <bits/stdc++.h>
using namespace std;
const int next_x[8] = {0, 1, -1, 0, 1, 1, -1, -1};
const int next_y[8] = {1, 0, 0, -1, 1, -1, -1, 1};
const int inf = 2147483640;
const long long linf = 1e15;
template <class T>
T fast_pow(T x, T k, T m) {
  T ans = 1;
  while (k) {
    if (k % 2 == 1) ans = ans * x % m;
    k = k / 2;
    x = x * x % m;
  }
  return ans;
}
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
int exgcd(int a, int b, int &x, int &y) {
  if (b == 0) {
    x = 1, y = 0;
    return a;
  }
  int d = exgcd(b, a % b, x, y);
  int t = x;
  x = y;
  y = t - a / b * y;
  return d;
}
bool exgcd_work(int a, int b, int &x, int &y, int c) {
  int g = exgcd(a, b, x, y);
  int _a = a / g, _b = b / g;
  if (c % g != 0) return 0;
  while (x <= 0) x += _a, y += _b;
  x *= c / g, y *= c / g;
  return 1;
}
template <class T>
T muti_gcd(T a[], int n) {
  T ans = a[1];
  for (int i = 2; i <= n; i++) ans = gcd(ans, a[i]);
  return ans;
}
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
void init_prime(bool not_prime[], int prime[], int &head, int n) {
  not_prime[1] = 1;
  for (int i = 2; i <= n; i++) {
    if (!not_prime[i]) prime[++head] = i;
    for (int j = 1; j <= head && (long long)prime[j] * i <= n; j++) {
      not_prime[prime[j] * i] = 1;
      if (i % prime[j] == 0) break;
    }
  }
}
bool is_prime(int x) {
  int t = sqrt(x);
  for (int i = 2; i <= t; i++)
    if (x % i == 0) return 0;
  return 1;
}
int crt(int n, int a[], int m[]) {
  int d = 1, x, y, ans = 0;
  for (int i = 1; i <= n; i++) d = d * m[i];
  for (int i = 1; i <= n; i++) {
    int M = d / m[i];
    exgcd(M, m[i], x, y);
    ans = (ans + M * x * a[i]) % d;
  }
  if (ans < 0) ans += d;
  return ans;
}
int get_phi(int n) {
  int ans = n, t = sqrt(n);
  for (int i = 2; i <= t; i++) {
    if (n % i == 0) {
      ans -= ans / i;
      while (n % i == 0) n /= i;
    }
  }
  if (n > 1) ans -= ans / n;
  return ans;
}
int init_phi() { return -1; }
long long euler(long long a, string b, long long m) {
  bool flag = 0;
  long long t = 0, phi_m = get_phi(m);
  for (string::iterator p = b.begin(); p != b.end(); p++) {
    t = t * 10 + (*p) - '0';
    if (t >= phi_m) t %= phi_m, flag = 1;
  }
  return flag ? fast_pow(a, t % phi_m + phi_m, m) : fast_pow(a, t, m);
}
template <size_t sz, long long MOD>
struct mat {
  int n, m;
  long long a[sz][sz];
  mat(int x = 0) { n = m = x, memset(this->a, 0, sizeof(this->a)); }
  mat(int x, int y) { n = x, m = y, memset(this->a, 0, sizeof(this->a)); }
  void unit(int x) {
    n = m = x;
    memset(a, 0, sizeof(a));
    for (int i = 1; i <= n; i++) a[i][i] = 1;
  }
  mat operator*(mat x) {
    mat res(n, x.m);
    if (m == x.n) {
      for (int k = 1; k <= m; k++)
        for (int i = 1; i <= n; i++)
          for (int j = 1; j <= x.m; j++)
            res.a[i][j] = (res.a[i][j] + a[i][k] * x.a[k][j] % MOD) % MOD;
    }
    return res;
  }
  void operator*=(mat x) { *this = (*this) * x; }
  void pow(long long k) {
    mat<sz, MOD> ans(n), x = (*this);
    ans.unit(ans.n);
    while (k) {
      if (k & 1) ans = ans * x;
      k = k >> 1, x = x * x;
    }
    (*this) = ans;
  }
  void print(bool flag = 0) {
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) printf("%lld ", a[i][j]);
      printf("\n");
    }
    if (flag)
      for (int i = 1; i <= n; i++) printf("-");
    if (flag) printf("\n");
  }
  void read() {
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= m; j++) scanf("%lld", &a[i][j]);
  }
};
long long get_inv(long long x, long long mod) {
  return fast_pow(x, mod - 2, mod);
}
template <size_t sz>
bool guass(double a[][sz], int n) {
  double t;
  int i = 1, to;
  const double eps = 1e-6;
  for (int i = 1; i <= n; i++) {
    for (to = i; to <= n; to++)
      if (fabs(a[to][i]) > eps) break;
    if (to > n) continue;
    if (to != i)
      for (int j = 1; j <= n + 1; j++) swap(a[to][j], a[i][j]);
    t = a[i][i];
    for (int j = 1; j <= n + 1; j++) a[i][j] /= t;
    for (int j = 1; j <= n; j++) {
      if (j == i) continue;
      t = a[j][i];
      for (int k = 1; k <= n + 1; k++) a[j][k] -= t * a[i][k];
    }
  }
  for (int i = 1; i <= n; i++)
    if (fabs(a[i][n + 1]) > eps) return 0;
  return 1;
}
template <size_t sz>
void guass(long long a[][sz], int n, int MOD) {
  long long t;
  int i = 1, to;
  for (int i = 1; i <= n; i++) {
    for (to = i; to <= n; to++)
      if (a[to][i]) break;
    if (to > n) continue;
    if (to != i)
      for (int j = 1; j <= n + 1; j++) swap(a[to][j], a[i][j]);
    t = get_inv(a[i][i], MOD);
    for (int j = 1; j <= n + 1; j++) a[i][j] *= t, a[i][j] %= MOD;
    for (int j = 1; j <= n; j++) {
      if (j == i) continue;
      t = a[j][i];
      for (int k = 1; k <= n + 1; k++)
        a[j][k] = ((a[j][k] - t * a[i][k] % MOD) % MOD + MOD) % MOD;
    }
  }
}
int read() {
  int t = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    t = t * 10 + ch - '0';
    ch = getchar();
  }
  return t * f;
}
extern const int MAXN = 2005;
extern const int N = 10000000;
int n;
long long f[MAXN][MAXN], ans = 0;
const int MOD = 1e9 + 7;
int work() {
  n = read();
  f[0][0] = 1;
  for (int i = 1; i <= 2 * n; i++) {
    for (int j = 0; j <= i; j++)
      f[i][j] = ((j ? f[i - 1][j - 1] : 0) + f[i - 1][j + 1]) % MOD;
    if ((i & 1))
      for (int j = 1; 2 * n - i >= j; j += 2) ans += f[i][j], ans %= MOD;
  }
  return printf("%lld\n", ans);
}
int main() {
  ios::sync_with_stdio(false);
  work();
  return 0;
}

### Prompt

Your task is to create a cpp solution to 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;
const int next_x[8] = {0, 1, -1, 0, 1, 1, -1, -1};
const int next_y[8] = {1, 0, 0, -1, 1, -1, -1, 1};
const int inf = 2147483640;
const long long linf = 1e15;
template <class T>
T fast_pow(T x, T k, T m) {
  T ans = 1;
  while (k) {
    if (k % 2 == 1) ans = ans * x % m;
    k = k / 2;
    x = x * x % m;
  }
  return ans;
}
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
int exgcd(int a, int b, int &x, int &y) {
  if (b == 0) {
    x = 1, y = 0;
    return a;
  }
  int d = exgcd(b, a % b, x, y);
  int t = x;
  x = y;
  y = t - a / b * y;
  return d;
}
bool exgcd_work(int a, int b, int &x, int &y, int c) {
  int g = exgcd(a, b, x, y);
  int _a = a / g, _b = b / g;
  if (c % g != 0) return 0;
  while (x <= 0) x += _a, y += _b;
  x *= c / g, y *= c / g;
  return 1;
}
template <class T>
T muti_gcd(T a[], int n) {
  T ans = a[1];
  for (int i = 2; i <= n; i++) ans = gcd(ans, a[i]);
  return ans;
}
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
void init_prime(bool not_prime[], int prime[], int &head, int n) {
  not_prime[1] = 1;
  for (int i = 2; i <= n; i++) {
    if (!not_prime[i]) prime[++head] = i;
    for (int j = 1; j <= head && (long long)prime[j] * i <= n; j++) {
      not_prime[prime[j] * i] = 1;
      if (i % prime[j] == 0) break;
    }
  }
}
bool is_prime(int x) {
  int t = sqrt(x);
  for (int i = 2; i <= t; i++)
    if (x % i == 0) return 0;
  return 1;
}
int crt(int n, int a[], int m[]) {
  int d = 1, x, y, ans = 0;
  for (int i = 1; i <= n; i++) d = d * m[i];
  for (int i = 1; i <= n; i++) {
    int M = d / m[i];
    exgcd(M, m[i], x, y);
    ans = (ans + M * x * a[i]) % d;
  }
  if (ans < 0) ans += d;
  return ans;
}
int get_phi(int n) {
  int ans = n, t = sqrt(n);
  for (int i = 2; i <= t; i++) {
    if (n % i == 0) {
      ans -= ans / i;
      while (n % i == 0) n /= i;
    }
  }
  if (n > 1) ans -= ans / n;
  return ans;
}
int init_phi() { return -1; }
long long euler(long long a, string b, long long m) {
  bool flag = 0;
  long long t = 0, phi_m = get_phi(m);
  for (string::iterator p = b.begin(); p != b.end(); p++) {
    t = t * 10 + (*p) - '0';
    if (t >= phi_m) t %= phi_m, flag = 1;
  }
  return flag ? fast_pow(a, t % phi_m + phi_m, m) : fast_pow(a, t, m);
}
template <size_t sz, long long MOD>
struct mat {
  int n, m;
  long long a[sz][sz];
  mat(int x = 0) { n = m = x, memset(this->a, 0, sizeof(this->a)); }
  mat(int x, int y) { n = x, m = y, memset(this->a, 0, sizeof(this->a)); }
  void unit(int x) {
    n = m = x;
    memset(a, 0, sizeof(a));
    for (int i = 1; i <= n; i++) a[i][i] = 1;
  }
  mat operator*(mat x) {
    mat res(n, x.m);
    if (m == x.n) {
      for (int k = 1; k <= m; k++)
        for (int i = 1; i <= n; i++)
          for (int j = 1; j <= x.m; j++)
            res.a[i][j] = (res.a[i][j] + a[i][k] * x.a[k][j] % MOD) % MOD;
    }
    return res;
  }
  void operator*=(mat x) { *this = (*this) * x; }
  void pow(long long k) {
    mat<sz, MOD> ans(n), x = (*this);
    ans.unit(ans.n);
    while (k) {
      if (k & 1) ans = ans * x;
      k = k >> 1, x = x * x;
    }
    (*this) = ans;
  }
  void print(bool flag = 0) {
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) printf("%lld ", a[i][j]);
      printf("\n");
    }
    if (flag)
      for (int i = 1; i <= n; i++) printf("-");
    if (flag) printf("\n");
  }
  void read() {
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= m; j++) scanf("%lld", &a[i][j]);
  }
};
long long get_inv(long long x, long long mod) {
  return fast_pow(x, mod - 2, mod);
}
template <size_t sz>
bool guass(double a[][sz], int n) {
  double t;
  int i = 1, to;
  const double eps = 1e-6;
  for (int i = 1; i <= n; i++) {
    for (to = i; to <= n; to++)
      if (fabs(a[to][i]) > eps) break;
    if (to > n) continue;
    if (to != i)
      for (int j = 1; j <= n + 1; j++) swap(a[to][j], a[i][j]);
    t = a[i][i];
    for (int j = 1; j <= n + 1; j++) a[i][j] /= t;
    for (int j = 1; j <= n; j++) {
      if (j == i) continue;
      t = a[j][i];
      for (int k = 1; k <= n + 1; k++) a[j][k] -= t * a[i][k];
    }
  }
  for (int i = 1; i <= n; i++)
    if (fabs(a[i][n + 1]) > eps) return 0;
  return 1;
}
template <size_t sz>
void guass(long long a[][sz], int n, int MOD) {
  long long t;
  int i = 1, to;
  for (int i = 1; i <= n; i++) {
    for (to = i; to <= n; to++)
      if (a[to][i]) break;
    if (to > n) continue;
    if (to != i)
      for (int j = 1; j <= n + 1; j++) swap(a[to][j], a[i][j]);
    t = get_inv(a[i][i], MOD);
    for (int j = 1; j <= n + 1; j++) a[i][j] *= t, a[i][j] %= MOD;
    for (int j = 1; j <= n; j++) {
      if (j == i) continue;
      t = a[j][i];
      for (int k = 1; k <= n + 1; k++)
        a[j][k] = ((a[j][k] - t * a[i][k] % MOD) % MOD + MOD) % MOD;
    }
  }
}
int read() {
  int t = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    t = t * 10 + ch - '0';
    ch = getchar();
  }
  return t * f;
}
extern const int MAXN = 2005;
extern const int N = 10000000;
int n;
long long f[MAXN][MAXN], ans = 0;
const int MOD = 1e9 + 7;
int work() {
  n = read();
  f[0][0] = 1;
  for (int i = 1; i <= 2 * n; i++) {
    for (int j = 0; j <= i; j++)
      f[i][j] = ((j ? f[i - 1][j - 1] : 0) + f[i - 1][j + 1]) % MOD;
    if ((i & 1))
      for (int j = 1; 2 * n - i >= j; j += 2) ans += f[i][j], ans %= MOD;
  }
  return printf("%lld\n", ans);
}
int main() {
  ios::sync_with_stdio(false);
  work();
  return 0;
}

```