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 ll long long
#define ld long double
#define db double
#define pint pair<int,int>
#define mk(x,y) make_pair(x,y)
#define fir first
#define sec second
#define Rep(x,y,z) for(int x=y;x<=z;++x)
#define Red(x,y,z) for(int x=y;x>=z;--x)
using namespace std;
const int Mod=1e9+7,MAXN=55;
char buf[1<<12],*p1=buf,*p2=buf,nc;int ny;
inline char gc() {return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<12,stdin),p1==p2)?EOF:*p1++;}
//inline char gc(){return getchar();}
inline int read(){
	int x=0;ny=1;while(nc=gc(),(nc<48||nc>57)&&nc!=EOF)if(nc==45)ny=-1;if(nc<0)return nc;
	x=nc-48;while(nc=gc(),47<nc&&nc<58&&nc!=EOF)x=(x<<3)+(x<<1)+(nc^48);return x*ny;
}
int n,C[MAXN][MAXN],F[MAXN][MAXN];
int main(){
//	freopen("std.in","r",stdin);
//	freopen("std.out","w",stdout);
	n=read();
	Rep(i,0,n){C[i][0]=1;Rep(j,1,i)C[i][j]=(C[i-1][j-1]+C[i-1][j])%Mod;}
	F[1][0]=F[1][1]=n;
	Rep(i,1,n-1)Rep(j,1,n-i)Rep(k,0,j)if(!((k^j)&1)){
		int x=(j-k)>>1;Rep(d,0,j)F[i+j][abs(x-d)]=(F[i+j][abs(x-d)]+1ll*F[i][k]*C[n-i][j]%Mod*C[j][d])%Mod;
	}cout<<F[n][0]<<'\n';
	return 0;
}


