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>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(x) (x).begin (),(x).end()
#define sqrt(x) sqrt(abs(x))
#define re return
#define sz(x) ((int)(x).size ())
#define prev PREV
#define next NEXT

using ll = long long;
using ii = pair<int, int>;
using ld = long double;
using D = double;
using vi = vector<int>;
using vii = vector<ii>;
using vvi = vector<vi>;
using vs = vector<string>;

template<typename T> T abs (T x) { re x < 0 ? -x : x; }
template<typename T> T sgn (T x) { re x < 0 ? -1 : (x > 0 ? 1 : 0); }
template<typename T> T sqr (T x) { re x * x; }
template<typename T> T gcd (T a, T b) { re a ? gcd (b % a, a) : b; }

const int mod = 1000*1000*1000+7;

int n;
int m;
int res[51][51][51][51];
int f[51];
int rf[51];

int power (int a, int b) {
	int c = 1;
	while (b) {
		if (b & 1) c = ((ll)c * a) % mod;
		a = ((ll)a * a) % mod;
		b /= 2;
	}
	re c;
}

int go (int lev, int now, int pos, int neg) {
	if (res[lev][now][pos][neg]) re res[lev][now][pos][neg];
	if (now == n) {
		int cur = ((ll)rf[pos] * rf[neg]) % mod;
//		printf ("%d %d %d %d = %d\n", lev, now, pos, neg, (int)((ll)cur * f[n - now + pos + neg] % mod));
		re cur;
	}	
	if (pos + neg == 0 || lev == n) re 0;
	int cur = 0;
	set<pair<ii, ii> > was;
	for (int apos = 0; apos <= pos && now + apos <= n; apos++)
		for (int aneg = 0; aneg <= neg && now + apos + aneg <= n; aneg++)
			for (int both = 0; now + apos + aneg + 2 * both <= n; both++) {
				int cpos = pos - apos + aneg;
				int cneg = neg - aneg + apos;
				int npos = apos + both;
				int nneg = aneg + both;
				if (was.count (mp (mp (cpos, cneg), mp (npos, nneg)))) continue;
				was.insert (mp (mp (cpos, cneg), mp (npos, nneg)));
				cur = (cur + (ll)go (lev + 1, now + apos + aneg + 2 * both, npos, nneg) * rf[cpos] % mod * rf[cneg]) % mod;
			}
//	printf ("%d %d %d %d = %d\n", lev, now, pos, neg, (int)((ll)cur * f[n - now + pos + neg] % mod));
	re res[lev][now][pos][neg] = cur;
}

int main () {
	scanf ("%d", &n);
	f[0] = rf[0] = 1;
	for (int i = 1; i <= n; i++) {
		f[i] = ((ll)f[i - 1] * i) % mod;
		rf[i] = power (f[i], mod - 2);
	}
	cout << ((ll)go (0, 1, 1, 0) * f[n]) % mod << endl;
//	cerr << clock () << endl;
	return 0;
}