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<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<string>
#include<stack>
#include<cstdio>
#include<cmath>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<int,P> P1;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define rep(i,x) for(int i=0;i<x;i++)
#define rep1(i,x) for(int i=1;i<=x;i++)
#define rrep(i,x) for(int i=x-1;i>=0;i--)
#define rrep1(i,x) for(int i=x;i>0;i--)
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
#define mp1(a,b,c) P1(a,P(b,c))

const int INF=1000000000;
const int dir_4[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
const int dir_8[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};

const ll M = 1000000007;

ll modpow(ll x,ll k){
	if(k == 0)return 1;
	ll tmp = modpow(x,k/2);
	tmp *= tmp; tmp %= M;
	if(k%2 == 1){
		tmp *= x;
		tmp %= M;
	}
	return tmp;
}

ll f[52];
ll f_inv[52];

int main(){
	f[0] = 1;
	for(int i = 1 ; i < 52 ; i ++){
		f[i] = f[i-1]*i;
		f[i] %= M;
	}
	for(int i = 0 ; i < 52 ; i ++){
		f_inv[i] = modpow(f[i],M-2);
	}
	
	ll N;
	cin >> N;
	
	ll ret = 0;
	static ll dp[52][52][52][52] = {};
	dp[0][1][1][0] = 1;
	for(int i = 0 ; i < 51 ; i ++){
		for(int j = 0 ; j <= N ; j ++){
			for(int k = 0 ; k < 52 ; k ++){
				for(int l = 0 ; l < 52 ; l ++){
					if(dp[i][j][k][l] == 0)continue;
					//cout << i << " " << j << " " << k << " " << l << " " << dp[i][j][k][l] << endl;
					if(j == N){
						dp[i][j][k][l] %= M;
						dp[i][j][k][l] *= f_inv[k]; dp[i][j][k][l] %= M;
						dp[i][j][k][l] *= f_inv[l]; dp[i][j][k][l] %= M;
						ret += dp[i][j][k][l]; if(ret>=M)ret-=M; continue;
					}
					dp[i][j][k][l] %= M;
					for(int s = 0 ; s < 52 ; s ++){
						for(int t = 0 ; t < 52 ; t ++){
							if(s+t == 0 || k+t-s < 0 || l+s-t < 0)continue;
							if(j+s+t > N)continue;
							ll hoge = f_inv[k+t-s]*f_inv[l+s-t]; hoge %= M;
							hoge *= dp[i][j][k][l]; hoge %= M;
							dp[i+1][j+s+t][s][t] += hoge;
						}
					}
				}
			}
		}
	}
	cout << (ret*f[N])%M << endl;
}

