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
/*
边权为 -1, 2 的二叉树转多叉树，使得 $(-1) ^ {c_i} 2 ^ {d_i}$ 中的 $d_i$ 只与深度有关

父亲对自己的正负号贡献和儿子对自己的正负号贡献拆开，分别为“树权”和“点权”

分类讨论并转移，$O(n ^ 5)$，什么鬼差分后优化为 $O(n ^ 4)$

方案不同当且仅当存在点 “终权” = 树权 * 点权 在两种方案中不同，或者 深度相同的点的进制 在两种方案中不同

于是本题统计方案时要特别注意，无论是树权的组合，还是点权的组合，对于方案数都是没有贡献的，
于是，第 i 层的方案分为两部分，“终权”和点数，点数是需要在转移到第 i 层的时候计算好的，
但是有树权为 1 的点数对答案是没有贡献的，只有在转移到 i + 1 层的时候，才能确定第 i 层的“终权”，
这时才能算上“终权”的贡献，最后一层终权 = 树权，特殊统计

其实，这题也可以看做是一种有“后效性”的 DP，因为第 i + 1 层的情况会对第 i 层的情况产生影响。
一般有后效性的 DP 使用高斯消元，而这一题利用不变量和类似待定系数的方法，把贡献拆到了下一层计算，
而 i + 2 行以后的情况对 i 行无影响；同时在最后层时 DP 无后效性，解决了这个问题。是一个不错的思路

(j - k, -1, x, - 1) (k, 1, y, -1)
[x + k - y, 1] [y + j - k - x, -1]

ntk - (ntj - ntk) = y - x   ntj = 2 * ntk - (y - x)
*/
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 55, Mod = 1e9 + 7;

int n, fans, C[N][N], f[N][N][N];

/* f[i][j][k] ：i 个点，最后一层 j 个点，最后一层有 k 个树权为 1 */
inline void Add(int &x, LL y) { x = ((LL)x + y) % Mod; }

int main()
{
	scanf("%d", &n);
	for (int i = 0; i <= n; ++i) {
		C[i][0] = C[i][i] = 1;
		for (int j = 1; j < i; ++j)
			C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % Mod;
	}
	//f[1][1][1] = 1;
	f[1][1][1] = C[n][1];
	for (int i = 1; i < n; ++i)
	for (int j = 1; j <= i; ++j)
	for (int k = 0; k <= j; ++k) {
		for (int deta = -(j - k); deta <= k; ++deta)
		for (int ntk = 0; i + ntk <= n; ++ntk) {
			int ntj = 2 * ntk - deta;
			if (ntj < 0) continue;
			if (i + ntj > n) break;
			//Add(f[i + ntj][ntj][ntk], (LL)f[i][j][k] * C[n - i][ntj] % Mod * C[ntj][ntk] % Mod * C[j][k - deta]);
			Add(f[i + ntj][ntj][ntk], (LL)f[i][j][k] * C[n - i][ntj] % Mod * C[j][k - deta]);
		}
	}
	fans = 0;
	for (int i = 1; i <= n; ++i)
		for (int j = /*1*/ 0; j <= n; ++j) {
			//Add(fans, (LL)f[n][i][j]);
			Add(fans, (LL)f[n][i][j] * C[i][j]);
		}
	printf("%d\n", (fans % Mod + Mod) % Mod);

	return 0;
}
