## solution

DP。$O(N^2)$。

## implementation

#include <iostream>
#include <vector>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
typedef long long ll;
using namespace std;
template <typename T, typename X> auto vectors(T a, X x) { return vector<T>(x, a); }
template <typename T, typename X, typename Y, typename... Zs> auto vectors(T a, X x, Y y, Zs... zs) { auto cont = vectors<T, Y, Zs...>(a, y, zs...); return vector<decltype(cont)>(x, cont); }

ll powi(ll x, ll y, ll p) {
assert (y >= 0);
x = (x % p + p) % p;
ll z = 1;
for (ll i = 1; i <= y; i <<= 1) {
if (y & i) z = z * x % p;
x = x * x % p;
}
return z;
}
ll inv(ll x, ll p) {
assert ((x % p + p) % p != 0);
return powi(x, p-2, p);
}
const int mod = 1000000007;
ll choose(ll n, ll r) { // O(n) at first time, otherwise O(1)
static vector<ll> fact(1,1);
static vector<ll> ifact(1,1);
if (fact.size() <= n) {
int l = fact.size();
fact.resize( n + 1);
ifact.resize(n + 1);
repeat_from (i,l,n+1) {
fact[i]  = fact[i-1] * i % mod;
ifact[i] = inv(fact[i], mod);
}
}
r = min(r, n - r);
return fact[n] * ifact[n-r] % mod * ifact[r] % mod;
}

const int U = 0;
const int D = 1;
int main() {
int n; cin >> n;
vector<vector<vector<ll> > > dp = vectors<ll>(0, n+1, 2, 2);
if (n == 1 or n == 2) {
// nop
} else {
dp[0][U][D] = 1;
dp[0][D][U] = 1;
dp[1][U][U] = 1;
dp[1][D][D] = 1;
repeat_from (len,2,n+1) {
repeat (l,len) {
int r = len-1 - l;
assert (l + 1 + r == len and 0 <= l and l < len and 0 <= r and r < len);
repeat (x,2) repeat (y,2) {
dp[len][x][y] += dp[l][x][D] * dp[r][D][y] % mod * choose(l+r, l) % mod;
}
}
repeat (x,2) repeat (y,2) dp[len][x][y] %= mod;
}
}
ll ans = 0;
repeat (x,2) repeat (y,2) ans += dp[n][x][y];
cout << (ans % mod) << endl;
return 0;
}