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<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
ll mod = 1000000007;
#define SIZE 100000
ll inv[SIZE + 1];
ll kai[SIZE + 1];
ll invkai[SIZE + 1];
void invinit()
{
	inv[1] = 1;
	for (int i = 2; i <= SIZE; i++)
	{
		inv[i] = mod - (mod / i)*inv[mod%i] % mod;
	}
	kai[0] = invkai[0] = 1;
	for (int i = 1; i <= SIZE; i++)
	{
		kai[i] = kai[i - 1] * i%mod;
		invkai[i] = invkai[i - 1] * inv[i] % mod;
	}
}
ll com(ll a, ll b)
{
	if (b < 0 || a < b)return 0;
	return (invkai[b] * invkai[a - b]) % mod*kai[a] % mod;
}
ll dp[60][60][60][60];
ll ans[51] = { 0,
1,
2,
12,
84,
770,
8340,
106400,
1546888,
25343766,
461133960,
232367169,
627905865,
632459808,
928262728,
919805769,
382796331,
887217496,
639768068,
869694124,
205875097,
205589953,
487772376,
239955313,
998339621,
31622834,
902930073,
146839084,
449786840,
982224660,
865803735,
21834818,
721531716,
26008837,
471774471,
69010090,
700009308,
776938882,
645550477,
526939604,
142728157,
654489641,
128201240,
185493259,
789721045,
977049419,
589149550,
700648836,
25087729,
874433491,
352791804
};
int main()
{
	int num;
	scanf("%d", &num);
	printf("%lld\n", ans[num]);
	/*invinit();
	dp[num][0][0][0] = 1;
	for (int i = num - 1; i >= 0; i--)
	{
		for (int j = 0; j <= num; j++)
		{
			for (int k = 0; k <= j; k++)
			{
				for (int l = 0; l <= j - k; l++)
				{
					if (dp[i + 1][j][k][l] == 0)continue;
					for (int m = 0; m <= num - j; m++)
					{
						for (int n = 0; n <= num - j - m; n++)
						{
							if (k - l > n || l - k > m)continue;
							if (k + l > 0 && m + n == 0)continue;
							dp[i][j + m + n][m - l + k][n - k + l] = (dp[i][j + m + n][m - l + k][n - k + l] + dp[i + 1][j][k][l] * com(j + m, m) % mod*com(j + m + n, n)) % mod;
						}
					}
				}
			}
		}
	}
	for (int i = 0; i <= 50;i++)printf("%lld,\n", dp[0][i][1][0]);*/
}