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<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<queue>
#include<cmath>
#include<cstdlib>
#define LL long long
#define LD long double
using namespace std;
const int NN=100 +117;
const int MM=100000 +117;
const int mod=1e9+7;
int read(){
	int fl=1,x;char c;
	for(c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar());
	if(c=='-'){fl=-1;c=getchar();}
	for(x=0;c>='0'&&c<='9';c=getchar())
		x=(x<<3)+(x<<1)+c-'0';
	return x*fl;
}
void open(){
	freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout);
}
void close(){
	fclose(stdin);
	fclose(stdout);
}


int m,n;
LL dp[NN][2*NN]={};
LL fact[NN]={};
LL rev[NN]={};
LL ksm(LL a,LL b){
	LL ret=1;
	for(;b;b>>=1,a=a*a%mod)
		if(b&1)ret=ret*a%mod;
	return ret;
}
void prefact(int n){
	fact[0]=1;
	for(int i=1;i<=n;++i){
		fact[i]=fact[i-1]*i%mod;
	}
	rev[n]=ksm(fact[n],mod-2);
	for(int i=n;i>=1;--i){
		rev[i-1]=rev[i]*i%mod;
	}
}
int main(){
	//open();
	n=read();
	int std=n;
	dp[1][std-1]=1;
	dp[1][std]=1;
	prefact(n);
	for(int i=1;i<n;++i){
		for(int j=0;j<=2*n;++j){
			int more=abs(j-std);
			int tp=j-std;
			for(int k=(more==0?2:more);k+i<=n;k+=2){
				for(int c=0;c<=k;++c){
					int xt=(tp+k-2*c)/2;
					if(xt>=-n&&xt<=n){
						dp[i+k][std+xt]+=dp[i][j]*rev[k-c]%mod*rev[c];
						dp[i+k][std+xt]%=mod;
					}
				}
			}
		}
	}
	printf("%lld\n",dp[n][std]*fact[n]%mod);
	close();
	return 0;
}