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<cstdio>
#include<algorithm>
using namespace std;
int n;
long long D[51][51][51], TD[51][51][51], Next[51][51][51][51], Mod = 1000000007, Res, F[52], InvF[52];
long long Pow(long long a, long long b) {
	long long r = 1;
	while (b) {
		if (b & 1)r = r*a%Mod;
		a = a*a%Mod;
		b >>= 1;
	}
	return r;
}
void Go() {
	Res = (Res+D[n][0][0])%Mod;
	int i, j, k;
	for (i = 0; i <= n; i++) {
		for (j = 0; i + j <= n; j++) {
			for (k = 0; i + j + k <= n; k++) {
				if (!D[i][j][k])continue;
				int ii = j + k + i;
				if (ii > n || i==ii)continue;
				for (int jj = 0; jj <= n; jj++)for (int kk = 0; ii + jj + kk <= n; kk++) {
					TD[ii][jj][kk] = (TD[ii][jj][kk] + D[i][j][k] * Next[j][k][jj][kk]) % Mod;
				}
			}
		}
	}
	for (i = 0; i <= n; i++)for (j = 0; i + j <= n; j++)for (k = 0; i + j + k <= n; k++) {
		D[i][j][k] = TD[i][j][k];
		TD[i][j][k] = 0;
	}
}
void Calc(int x, int y){
	int i, j, k;
	if (x + y == 0)return;
	for (i = 0; i <= n; i++)for (j = 0; i+j+x+y <= n; j++) {
		k = x + j - i;
		if (k >= 0 && k <= x + y) {
			Next[x][y][i][j] = InvF[k] * InvF[x + y - k]%Mod;
		}
	}
}
int main() {
	int i, j, k;
	scanf("%d", &n);
	F[0] = InvF[0] = 1;
	for (i = 1; i <= 50; i++) {
		F[i] = F[i - 1] * i%Mod;
		InvF[i] = Pow(F[i], Mod - 2);
	}
	for (i = 0; i < n; i++) {
		D[1][(i + 1) / 2][i / 2] = 1;
	}
	for (i = 0; i <= n; i++)for (j = 0; i + j <= n; j++)Calc(i, j);
	for (i = 0; i <= n; i++) Go();
	printf("%lld\n", Res*F[n]%Mod);
}