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>

using namespace std;
const int MOD(1000000000 + 7);
const int Max_N(55);

constexpr int Mult(int a, int b)
{
	return a * 1LL * b % MOD;
}

constexpr int Add(int a, int b)
{
	return a + b >= MOD ? a + b - MOD : a + b;
}

constexpr int Sub(int a, int b)
{
	return a < b ? a - b + MOD : a - b;
}

inline void upd(int &a, int b)
{
	a = Add(a, b);
}

constexpr int Abs(int x)
{
	return x >= 0 ? x : -x;
}

int N, C[Max_N][Max_N], F[Max_N][Max_N];//F[n][x]±íÊ¾µ±Ç°¿¼ÂÇµÄÇ°Èô¸É²ãÒ»¹²ÓÐn¸öµã£¬×îºóÒ»²ãÓÐx¸öÐèÒªÆæÊý¸ö¶ù×ÓµÄµã 

int main()
{
	scanf("%d", &N);
	C[0][0] = 1;
	for (int i = 1;i <= N;++i)
	{
		C[i][0] = C[i][i] = 1;
		for (int j = 1;j < i;++j)
			C[i][j] = Add(C[i - 1][j - 1], C[i - 1][j]);
	}
	F[1][0] = F[1][1] = N;
	for (int n = 1;n <= N;++n)
		for (int x = 0;x <= n;++x)
			for (int a = 0;n + a <= N;++a)
				for (int b = 0, xs;n + a + b <= N;++b)
				{
					if (a == 0 && b == 0)
						continue;
					if (a + b < x || (((a + b) & 1) ^ (x & 1)))
						continue;
					xs = Mult(C[N - n][a + b], C[a + b][a]);
					/*
					ÐÂµÄÒ»²ãÒ»¹²ÓÐa + b¸öµã¡£ÆäÖÐÓÐa¸öºÍ¸¸Ç×Õý¸º1ÏµÊýÏàÍ¬£¬ÁíÍâÓÐb¸ö²»ÏàÍ¬
					Ê×ÏÈÄÃ³öÀ´x¸öµã¹ÒÔÚÆæµãµÄ×îºó£¬È»ºó³ÉË«µÄ³öÏÖ
					Å¼Êý±àºÅµÄÎ»ÖÃ»áÇ¿ÖÆÈ¡·´£¬ËùÒÔÓÐ(a + b - x) / 2¸öÒÑ¾­±»È¡·´ÁË
					ÒòÎªÒªÇ¡ºÃÈ¡·´b¸ö£¬ËùÒÔ»áÓÐAbs((a + b - x) / 2 - b)¸öÆæµã 
					*/
					upd(F[n + a + b][Abs((a + b - x) / 2 - b)], Mult(xs, F[n][x]));
				}
	printf("%d", F[N][0]);
	return 0;
}