#include "bits/stdc++.h"
using namespace std;
template<int MOD>
struct Integral {
int v_ = 0;
// Implicit conversion is allowed.
Integral(int v) : v_(norm(v)) {}
Integral(long long v) : v_(norm(v)) {}
Integral(unsigned int v) : v_(norm(v)) {}
Integral(unsigned long long v) : v_(norm(v)) {}
Integral() = default;
~Integral() = default;
template<typename T> T norm(T v) const {
if constexpr(sizeof(T) > sizeof(MOD)) {
v %= MOD;
if (v < 0) v += MOD;
} else {
if (v >= MOD) v -= MOD;
if (v < 0) v += MOD;
if (v >= MOD || v < 0) {
v %= MOD;
if (v < 0) v += MOD;
}
}
return v;
}
int val() const { return v_; }
Integral& operator+=(const Integral& rhs) { v_ += rhs.val(); if (v_ >= MOD) v_ -= MOD; return *this; }
Integral& operator-=(const Integral& rhs) { v_ += MOD - rhs.val(); if (v_ >= MOD) v_ -= MOD; return *this; }
Integral& operator*=(const Integral& rhs) { v_ = v_ * 1LL * rhs.val() % MOD; return *this; }
Integral& operator/=(const Integral& rhs) { v_ = v_ * 1LL * rhs.inv().val() % MOD; return *this; }
Integral operator+(const Integral& rhs) const { Integral ret = *this; return ret += rhs; }
Integral operator-(const Integral& rhs) const { Integral ret = *this; return ret -= rhs; }
Integral operator*(const Integral& rhs) const { Integral ret = *this; return ret *= rhs; }
Integral operator/(const Integral& rhs) const { Integral ret = *this; return ret /= rhs; }
bool operator==(const Integral& rhs) const { return val() == rhs.val(); }
bool operator!=(const Integral& rhs) const { return !(*this == rhs); }
const Integral operator-() const { return Integral(-val()); }
const Integral& operator++() { v_ += 1; if (v_ >= MOD) v_ -= MOD; return *this; }
const Integral operator++(int) { Integral ret = *this; ++(*this); return ret; }
const Integral& operator--() { v_ += MOD - 1; if (v_ >= MOD) v_ -= MOD; return *this; }
const Integral operator--(int) { Integral ret = *this; --(*this); return ret; }
Integral power(long long b) const {
long long ret = 1 % MOD, a = v_;
for ( ; b; b >>= 1, a = a * a % MOD) if (b & 1) ret = ret * a % MOD;
return ret;
}
Integral inv() const { return power(MOD - 2); }
std::string to_string() const { return std::string("{") + std::to_string(val()) + "}"; }
};
const int MOD = 1e9 + 7;
using Mint = Integral<MOD>;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
string p = "((())";
int m = p.size();
vector<vector<vector<Mint>>> dp(n + 1, vector<vector<Mint>>(m + 1, vector<Mint>(n / 2 + 1, 0)));
dp[0][0][0] = 1;
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= m; ++j) {
for (int balance = 0; 2 * balance <= n; ++balance) {
if (j == m) {
dp[i + 1][j][balance + 1] += dp[i][j][balance];
if (balance > 0) {
dp[i + 1][j][balance - 1] += dp[i][j][balance];
}
} else if (p[j] == '(') {
dp[i + 1][j + 1][balance + 1] += dp[i][j][balance];
if (balance > 0) {
dp[i + 1][0][balance - 1] += dp[i][j][balance];
}
} else {
if (p[j - 1] == '(') {
dp[i + 1][j][balance + 1] += dp[i][j][balance];
} else {
dp[i + 1][1][balance + 1] += dp[i][j][balance];
}
if (balance > 0) {
dp[i + 1][j + 1][balance - 1] += dp[i][j][balance];
}
}
}
}
}
cout << dp[n][m][0].val() << '\n';
return 0;
}
Copy