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
//%std
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const int mod = 1e9 + 7, N = 52, O = 50;
int fpow(int base, int v) {
	int tot = 1;
	for(; v; v >>= 1, base = 1LL * base * base % mod) if (v & 1) tot = 1LL * tot * base % mod;
	return tot;
}
void upd(int&a, int b) { a = (a + b) % mod; }
int n, fac[N], ifac[N], dp[N][2 * N];
int main ()
{
	scanf("%d", &n);
	fac[0] = 1; rep(i, 1, 50) fac[i] = 1LL * fac[i - 1] * i % mod;
	ifac[50] = fpow (fac[50], mod - 2);
	per(i, 49, 0) ifac[i] = 1LL * ifac[i + 1] * (i + 1) % mod;
	dp[0][O + 1] = 1;
	rep(i, 0, n - 1) {
		if (i == 0) {
			int x = 1, y = 0;
			rep(d, -y, x) upd (dp[i + x + y][O + d], 1LL * ifac[x - d] * ifac[y + d] % mod * dp[i][O + x - y] % mod);
			continue;
		}
		rep(x, 0, n - i) rep(y, 0, n - i - x) if (x + y > 0) rep(d, -y, x) upd (dp[i + x + y][O + d], 1LL * ifac[x - d] * ifac[y + d] % mod * dp[i][O + x - y] % mod);
	}
	int ans = 1LL * fac[n] * dp[n][O] % mod;
	printf ("%d\n", ans);
	return 0;
}