Let X = 10^{100}. Inaba has N checker pieces on the number line, where the i-th checker piece is at coordinate X^{i} for all 1 \leq i \leq N.

Every second, Inaba chooses two checker pieces, A and B, and move A to the symmetric point of its current position with respect to B. After that, B is removed. (It is possible that A and B occupy the same position, and it is also possible for A to occupy the same position as another checker piece after the move).

After N - 1 seconds, only one checker piece will remain. Find the number of distinct possible positions of that checker piece, modulo 10^{9} + 7.

Constraints

* 1 \leq N \leq 50
* N is an integer.

Input

Input is given from Standard Input in the following format:


N


Output

Print the number of distinct possible positions of the final checker piece, modulo 10^{9} + 7.

Examples

Input

3


Output

12


Input

4


Output

84


Input

22


Output

487772376
#include <bits/stdc++.h>

#ifndef LOCAL
#define cerr dolor_sit_amet
#endif

#define mp make_pair
#define sz(x) ((int)((x).size()))
#define X first
#define Y second
#define all(x) (x).begin(), (x).end()

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair < int , int > ipair;
typedef pair < ll , ll > lpair;
const int IINF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fll;
const double DINF = numeric_limits<double>::infinity();
const int MOD = 1000000007;
const double EPS = 1e-9;
const double PI = acos(-1.0);
const int DX[] = { 1,  0, -1,  0,  1, -1,  1, -1};
const int DY[] = { 0,  1,  0, -1,  1, -1, -1,  1};
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll sqr(ll x) { return x*x; } ll sqr(int x) { return (ll)x*x; }
double sqr(double x) { return x*x; } ld sqr(ld x) { return x*x; }
mt19937 mmtw(960172);
ll rnd(ll x, ll y) { static uniform_int_distribution<ll> d; return d(mmtw) % (y - x + 1) + x; }

// ========================================================================= //

const int N = 55;

int pw(int a, int b) {
    int r = 1;
    for (; b; b >>= 1) {
        if (b & 1)
            r = 1LL * r * a % MOD;
        a = 1LL * a * a % MOD;
    }
    return r;
}
ll fact[N], ofact[N];

ll cnk(int n, int k) {
    if (n < k || k < 0)
        return 0;
    return fact[n] * ofact[k] % MOD * ofact[n-k] % MOD;
}

static ll d[N][N][N];
ll solve(int n, int x, int y) {
    ll &cd = d[n][x][y];
    if (cd != -1)
        return cd;
    if (n == 0)
        return cd = 1;
    if (x + y == 0)
        return cd = 0;
    cd = 0;
    for (int sx = 0; sx + x + y <= n; ++sx)
        for (int sy = 0; sx + sy + x + y <= n; ++sy) {
            int c1 = x - sx + sy, c2 = y - sy + sx;
            if (c1 < 0 || c2 < 0)
                continue;
            ll nd = solve(n - x - y, sx, sy);
            nd = nd * cnk(n, c1) % MOD;
            nd = nd * cnk(n-c1, c2) % MOD;
            cd = (cd + nd) % MOD;
        }
    return cd;
}
int main() {
    fact[0] = 1;
    for (int i = 1; i < N; ++i)
        fact[i] = fact[i - 1] * i % MOD;
    for (int i = 0; i < N; ++i)
        ofact[i] = pw(fact[i], MOD - 2);


    memset(d, -1, sizeof(d));
    int n;
    cin >> n;
    cout << solve(n, 1, 0) << "\n";


    return 0;
}
