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 <stdio.h>
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <time.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:336777216")
using namespace std;

#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define ldb ldouble

typedef tuple<int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;

int IT_MAX = 1 << 17;
int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-10;
#define szz(x) (int)(x).size()
#define rep(i, n) for(int i=0;i<n;i++)
#define Se second
#define Fi first

const int MX = 52;
const int MM = 1000000007;

void add(int &x, int y){ x = (x+y >= MM? x+y-MM : x+y); }

ll I[MX], FI[MX], F[MX];
int ans = 0;

int D[MX][MX][MX][MX];
int H[MX][MX][MX][MX];
int N;

ll get_value(int a, int b, int p, int q){
	int x = a, y = b;
	int d = p-q;
	x -= d, y += d;
	if(x < 0 || y < 0) return 0;
	return FI[x] * FI[y] % MM;
}

int main()
{
	I[1] = F[0] = FI[0] = 1;
	for(int i = 2; i < MX; i++) I[i] = (MM - MM/i) * I[MM%i] % MM;
	for(int i = 1; i < MX; i++){
		F[i] = F[i-1] * i % MM;
		FI[i] = FI[i-1] * I[i] % MM;
	}
	scanf("%d", &N);
	H[0][0][0][0] = 1;
	for(int i = 0; i <= N; i++){
		for(int j = 0; i+j <= N; j++){
			for(int a = 0; a <= N; a++){
				for(int b = 0; a+b <= N; b++){
					if(!H[i][j][a][b]) continue;
					for(int l = 0; l <= N; l++){
						if(a+(l+1)/2 <= N && b+l/2 <= N) H[i+1][j][a+(l+1)/2][b+l/2] |= H[i][j][a][b];
						if(!i && a+l/2 <= N && b+(l+1)/2 <= N) H[i][j+1][a+l/2][b+(l+1)/2] |= H[i][j][a][b];
					}
				}
			}
		}
	}
	D[0][0][1][0] = 1;
	for(int i = 0; i <= N; i++){
		for(int j = 0; j <= N; j++){
			for(int k = 0; j+k <= N; k++){
				for(int l = 0; j+k+l <= N; l++){
					if(!D[i][j][k][l]) continue;
					for(int p = 0; j+k+l+p <= N; p++){
						for(int q = 0; j+k+l+p+q <= N; q++){
							add(D[i+1][j+k+l][p][q], (ll)D[i][j][k][l] * H[k][l][p][q] % MM * get_value(k, l, p, q) % MM);
						}
					}
				}
			}
		}
	}
	printf("%lld\n", D[N][N][0][0] * F[N] % MM);
}
