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>
using namespace std;
#define cs const
#define pb push_back
#define ll long long 
#define pii pair<int,int>
#define fi first
#define se second
#define bg begin
cs int RLEN=(1<<20)|3;
inline char gc(){
	static char ibuf[RLEN],*ib,*ob;
	(ib==ob)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
	return (ib==ob)?EOF:*ib++;
}
inline int read(){
	char ch=gc();
	int res=0;bool f=1;
	while(!isdigit(ch))f^=ch=='-',ch=gc();
	while(isdigit(ch))res=(res*10)+(ch^48),ch=gc();
	return f?res:-res;
}
inline ll readll(){
	char ch=gc();
	ll res=0;bool f=1;
	while(!isdigit(ch))f^=ch=='-',ch=gc();
	while(isdigit(ch))res=(res*10)+(ch^48),ch=gc();
	return f?res:-res;	
}
inline int readstring(char *s){
	char ch=gc();int l=0;
	while(isspace(ch))ch=gc();
	while(!isspace(ch)&&ch!=EOF)s[++l]=ch,ch=gc();
	return l;
}
inline char readchar(){
	char ch=gc();
	while(isspace(ch))ch=gc();return ch;
}
template<typename tp>inline void chemx(tp &a,tp b){a<b?a=b:0;}
template<typename tp>inline void chemn(tp &a,tp b){a<b?a=b:0;}
cs int mod=1e9+7;
inline int add(int a,int b){return (a+b>=mod)?(a+b-mod):(a+b);}
inline int dec(int a,int b){return (a<b)?(a-b+mod):(a-b);}
inline int mul(int a,int b){static ll r;r=(ll)a*b;return (r>=mod)?(r%mod):r;}
inline void Add(int &a,int b){a=(a+b>=mod)?(a+b-mod):(a+b);}
inline void Dec(int &a,int b){a=(a<b)?(a-b+mod):(a-b);}
inline void Mul(int &a,int b){static ll r;r=(ll)a*b;a=(r>=mod)?(r%mod):r;}
inline int ksm(int a,int b,int res=1){for(;b;b>>=1,Mul(a,a))(b&1)&&(Mul(res,a),1);return res;}
inline int Inv(int x){return ksm(x,mod-2);}
cs int N=55;
int c[N][N],n,f[N][N];
inline void init_c(){
	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],c[i-1][j-1]);
	}
}
int main(){
	#ifdef Stargazer
	freopen("lx.in","r",stdin);
	#endif
	init_c();
	n=read();
	f[1][0]=f[1][1]=n;
	for(int i=1;i<n;i++)
	for(int j=0;j<=i;j++)
	for(int k=max(1,j);i+k<=n;k++)if(!((k-j)&1)){
		int v=(k-j)>>1;
		for(int l=0;l<=k;l++)
		Add(f[i+k][abs(v-l)],mul(c[n-i][k],mul(c[k][l],f[i][j])));
	}cout<<f[n][0]<<'\n';return 0;
}