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<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define SZ(x) ((int)x.size())
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
inline void read(int &x) {
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
inline ui R() {
	static ui seed=416;
	return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
const int N = 55,mo=1e9+7;
int n,f[N][N][N],C[N][N];
inline int getz(int x){return x>0?x:0;}
inline void add(int &x, int y){x=x+y<mo?x+y:x+y-mo;}
int main() {
	read(n);rep(i,0,n){
		C[i][0]=C[i][i]=1;
		rep(j,1,i-1)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mo;
	}
	f[0][1][0]=1;
	rep(x,0,n)rep(a,0,n)rep(b,0,n)if(f[x][a][b]&&x+a+b<=n&&a+b)rep(A,0,a+b){
		//if(!A)printf("%d %d %d:%d\n",x,a,b,f[x][a][b]);
		int B=a+b-A,aa=getz(a-A),bb=getz(A-a),t=1LL*f[x][a][b]*C[n-x][A]%mo*C[n-x-A][B]%mo;
		rep(k,0,n>>1)add(f[x+a+b][aa+k][bb+k],t);
	}
	printf("%d\n",f[n][0][0]);
	return 0;
}
