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>
#include <cassert>
#include <cstring>
#include <algorithm>
#define meow(args...) fprintf(stderr, args)
#define inc(x, y) (x=(x+y)%p)
typedef unsigned long long QWORD;
template<class Type> inline bool cmin(Type &a, const Type &b) {return b<a?(a=b, 1):0;}
template<class Type> inline bool cmax(Type &a, const Type &b) {return a<b?(a=b, 1):0;}
const unsigned p=1e9+7;
int n, fac[501], ifac[501], f[501][501], g[501][1001];
QWORD power(QWORD a, int b)
{
	QWORD ans=1;
	for(; b; a=a*a%p, b>>=1) if(b&1) ans=ans*a%p;
	return ans;
}
int main()
{
	int i, j, k;
	scanf("%d", &n);
	fac[0]=1;
	for(i=1; i<=n; ++i) fac[i]=(QWORD)fac[i-1]*i%p;
	ifac[n]=power(fac[n], p-2);
	for(i=n; i>=1; --i) ifac[i-1]=(QWORD)ifac[i]*i%p;
	f[1][0]=f[1][1]=fac[n];
	for(i=1; i<=n; ++i) {
		for(k=0; i+k<=n; ++k) for(j=k; j>=-n; j-=2) if(g[i][j+n]) inc(f[i+k][std::abs(j+k)/2], (QWORD)g[i][j+n]*ifac[k]);
		for(k=1; i+k<=n; ++k) for(j=0; j<=n&&j+3*k<=2*n; ++j) if(f[i][j]) inc(g[i+k][j-k+n], (QWORD)f[i][j]*ifac[k]);
		for(k=1; i+k<=n; ++k) for(j=k&1; j<=k&&j+3*k<=2*n; j+=2) if(f[i][j]) inc(f[i+k][(j+k)/2], (QWORD)f[i][j]*ifac[k]);
	}
	printf("%d\n", f[n][0]);
	return 0;
}
