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 <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
using namespace std;

#ifdef LOCAL
	#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
	#define eprintf(...) 42
#endif

typedef long long ll;
typedef pair<int, int> pii;
#define mp make_pair

typedef vector<int> vec;

const ll MOD = (ll)1e9 + 7;
ll add(ll x, ll y) {
	x += y;
	if (x >= MOD) return x - MOD;
	return x;
}
ll sub(ll x, ll y) {
	x -= y;
	if (x < 0) return x + MOD;
	return x;
}
ll mult(ll x, ll y) {
	return (x * y) % MOD;
}

const int N = 51;
const int NN = N + 5;
ll C[NN][NN];
ll dp[NN][NN][NN];
bool inner[NN][NN][NN][NN][NN];
ll prec[NN][NN][NN][NN];

void precalc() {
	for (int i = 0; i < N; i++)
		C[i][0] = C[i][i] = 1;
	for (int i = 1; i < N; i++)
		for (int j = 1; j < i; j++)
			C[i][j] = add(C[i - 1][j], C[i - 1][j - 1]);

	inner[0][0][0][0][0] = 1;
	for (int a = 0; a < N; a++)
		for (int b = 0; a + b < N; b++) {
			//cerr << a << " " << b << endl;
			for (int x = 0; x < N; x++) {
				for (int y = 0; y < N; y++)
					for (int z = 0; x + y + z < N; z++) {
						int ny = y + x / 2;
						int nz = z + (x + 1) / 2;
						int dt = 1 ^ (x & 1);
						for (int t = 0; t <= a + b; t++) {
							if (!inner[a][b][y][z][t]) continue;
							inner[a + 1][b][ny][nz][t + dt] = 1;
						}
						ny = y + (x + 1) / 2;
						nz = z + x / 2;
						dt ^= 1;
						for (int t = 0; t <= a + b; t++) {
							if (!inner[a][b][y][z][t]) continue;
							inner[a][b + 1][ny][nz][t + dt] = 1;
						}
					}
			}
		}
	
	for (int x = 0; x < N; x++)
		for (int y = 0; x + y < N; y++)
			for (int nx = 0; nx < N; nx++)
				for (int ny = 0; nx + ny < N; ny++) {
					prec[x][y][nx][ny] = 0;
					for (int t = 0; t < N; t++)
						if (inner[x][y][nx][ny][t])
							prec[x][y][nx][ny] = add(prec[x][y][nx][ny], C[x + y][t]);
				}
/*	
	for (int x = 0; x < 2; x++)
		for (int y = 0; y < 2; y++)
			for (int nx = 0; nx < 2; nx++)
				for (int ny = 0; ny < 2; ny++) {
					printf("prec[%d][%d][%d][%d] = %lld\n", x, y, nx, ny, prec[x][y][nx][ny]);
				}
*/
}

int main()
{
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);

	int ans[N];

	ans[1] = 1;
	ans[2] = 2;
	ans[3] = 12;
	ans[4] = 84;
	ans[5] = 770;
	ans[6] = 8340;
	ans[7] = 106400;
	ans[8] = 1546888;
	ans[9] = 25343766;
	ans[10] = 461133960;
	ans[11] = 232367169;
	ans[12] = 627905865;
	ans[13] = 632459808;
	ans[14] = 928262728;
	ans[15] = 919805769;
	ans[16] = 382796331;
	ans[17] = 887217496;
	ans[18] = 639768068;
	ans[19] = 869694124;
	ans[20] = 205875097;
	ans[21] = 205589953;
	ans[22] = 487772376;
	ans[23] = 239955313;
	ans[24] = 998339621;
	ans[25] = 31622834;
	ans[26] = 902930073;
	ans[27] = 146839084;
	ans[28] = 449786840;
	ans[29] = 982224660;
	ans[30] = 865803735;
	ans[31] = 21834818;
	ans[32] = 721531716;
	ans[33] = 26008837;
	ans[34] = 471774471;
	ans[35] = 69010090;
	ans[36] = 700009308;
	ans[37] = 776938882;
	ans[38] = 645550477;
	ans[39] = 526939604;
	ans[40] = 142728157;
	ans[41] = 654489641;
	ans[42] = 128201240;
	ans[43] = 185493259;
	ans[44] = 789721045;
	ans[45] = 977049419;
	ans[46] = 589149550;
	ans[47] = 700648836;
	ans[48] = 25087729;
	ans[49] = 874433491;
	ans[50] = 352791804;

	int n;
	cin >> n;
	cout << ans[n] << endl;
	return 0;

	precalc();

	for (int n = 1; n <= 50; n++) {

		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				for (int k = 0; k < N; k++)
					dp[i][j][k] = 0;

		dp[n][1][0] = 1;

		for (int leafs = n; leafs > 0; leafs--)
			for (int pos = 0; pos <= leafs; pos++)
				for (int neg = 0; neg + pos <= leafs; neg++) {
					if (dp[leafs][pos][neg] == 0) continue;
					if (pos + neg == 0) continue;
					int nleafs = leafs - pos - neg;
					ll cf = C[leafs][pos + neg];
					for (int npos = 0; npos <= nleafs; npos++)
						for (int nneg = 0; npos + nneg <= nleafs; nneg++)
							dp[nleafs][npos][nneg] = add(dp[nleafs][npos][nneg], mult(mult(prec[pos][neg][npos][nneg], cf), dp[leafs][pos][neg]));
				}

		printf("\tans[%d] = %lld;\n", n, dp[0][0][0]);
	}

	return 0;
}
