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 fo(i,a,b)for(int i=a,_e=b;i<=_e;++i)
#define fd(i,a,b)for(int i=b,_e=a;i>=_e;--i)
#define ll long long
#define add(x,y)(x=((ll)y+x)%mo)
using namespace std;
const int N=55,mo=1e9+7;
int n,jc[N],ny[N],iv[N][N],f[2][N][N+N],v,ans,o;
int ksm(int x,int y){
	int t=1;
	for(;y;y>>=1,x=(ll)x*x%mo)if(y&1)t=(ll)t*x%mo;
	return t;
}
int main(){
	cin>>n;
	jc[0]=1;
	fo(i,1,n)jc[i]=(ll)jc[i-1]*i%mo;
	ny[n]=ksm(jc[n],mo-2);
	fd(i,0,n-1)ny[i]=(ll)ny[i+1]*(i+1)%mo;
	fo(i,0,n)fo(j,0,n-i)iv[i][j]=(ll)ny[i]*ny[j]%mo;
	f[0][1][n]=1;
	f[0][1][n-1]=1;
	ans=f[0][n][n];
	fo(q,1,n-1){
		o^=1;memset(f[o],0,sizeof f[o]);
		fo(i,0,n)fo(j,-n,n)if(v=f[!o][i][n+j])
			fo(k,0,n-i)fo(l,0,n-i-k)
				if(k+l&&-k-l<=j&&j<=k+l&&!(j+k+l&1)&&-n-n<=j+k-l&&j+k-l<=n+n)
					add(f[o][i+k+l][n+(j+k-l>>1)],v*iv[k][l]);
		ans=(ans+f[o][n][n])%mo;
	}
	cout<<(ll)ans*jc[n]%mo;
}