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;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
ll dp[55][55][111];
ll c[55][55];
int n;
int main(){
	rep(i,55)rep(j,i+1){
		if(j==0||j==i)c[i][j]=1;
		else c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
	}
	cin>>n;
	dp[0][1][55+0] = dp[0][1][55-1] = n;
	for(int i=0;i<54;i++){
		for(int a=0;a<54;a++){
			for(int j=0;j<=110;j++){
				if(dp[i][a][j] == 0) continue;
				//1...,2^i -> 2^(i+1) * (j-55) + 1
				for(int k=0;k<=54-a;k++){
					for(int l=0;l<=54-a-k;l++){
						//2^(i+1) wo k ko
						//-2^(i+1) wo l ko
						if(k+l == 0) continue;
						if(a+k+l > n) continue;
						if(j-55-k-l <= 0 && 0 <= j-55+k+l){
							//1....2^(i+1) -> 2^(i+2) * ? + 1
							int x = j-55+k-l;
							if(x%2 == 0){
								dp[i+1][a+k+l][x/2+55] += dp[i][a][j]*c[n-a][k]%mod*c[n-a-k][l]%mod;
							}
						}
					}
				}
			}
		}
		for(int a=0;a<55;a++) for(int b=0;b<111;b++) dp[i+1][a][b] %= mod;
	}
	ll ans = 0;
	for(int i=0;i<55;i++) ans = (ans+dp[i][n][55])%mod;
	cout<<(ans+mod)%mod<<endl;
}