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
#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#endif

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <cassert>
#include <string.h>
#include <unordered_set>
#include <unordered_map>

using namespace std;

typedef long long int64;
typedef unsigned long long uint64;
#define two(X) (1<<(X))
#define twoL(X) (((int64)(1))<<(X))
#define contain(S,X) (((S)&two(X))!=0)
#define containL(S,X) (((S)&twoL(X))!=0)
const double pi=acos(-1.0);
const double eps=1e-11;
template<class T> inline void ckmin(T &a,T b){if(b<a) a=b;}
template<class T> inline void ckmax(T &a,T b){if(b>a) a=b;}
template<class T> inline T sqr(T x){return x*x;}
typedef pair<int,int> ipair;
#define SIZE(A) ((int)A.size())
#define LENGTH(A) ((int)A.length())
#define MP(A,B) make_pair(A,B)
#define PB(X) push_back(X)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,a) for(int i=0;i<(a);++i)
#define ALL(A) A.begin(),A.end()

template<typename base_type, base_type _MOD>
class IntMod
{
public:
	static const int INVERSE_CACHE_SIZE = (1 << 20);
	static base_type MOD;
	static void set_mod(base_type new_mod) { MOD = new_mod; }

	base_type n;

	IntMod(base_type d = 0) { n = (d >= 0 ? d % MOD : (d % MOD + MOD) % MOD); }
	virtual ~IntMod() = default;

	IntMod operator-() const { return Build(n == 0 ? 0 : MOD - n); }
	IntMod& operator+=(IntMod a) { n = (n >= MOD - a.n ? n - MOD + a.n : n + a.n); return *this; }
	IntMod& operator-=(IntMod a) { n = (n >= a.n) ? n - a.n : n - a.n + MOD; return *this; }
	IntMod& operator*=(IntMod a) { *this = *this * a; return *this; }
	IntMod& operator/=(IntMod a) { *this = *this / a; return *this; }

	static IntMod build(base_type n) { IntMod r; r.n = n; return r; }

	static base_type inverse_cache[INVERSE_CACHE_SIZE];
	static bool inverse_cache_ready;
	friend IntMod inverse(IntMod n) { return build(inverse_internal(n.n)); }
	static base_type inverse_internal(base_type n)
	{
		if (!inverse_cache_ready)
		{
			inverse_cache_ready = true;
			inverse_cache[0] = 0;
			inverse_cache[1] = 1;
			for (int n = 2; n < INVERSE_CACHE_SIZE; ++n) inverse_cache[n] = (MOD - (base_type)((long long)inverse_cache[MOD % n] * (MOD / n) % MOD));
		}
		return n < INVERSE_CACHE_SIZE ? inverse_cache[n] : MOD - (base_type)((long long)inverse_internal(MOD % n) * (MOD / n) % MOD);
	}

	friend bool operator==(IntMod a, IntMod b) { return a.n == b.n; }
	friend bool operator!=(IntMod a, IntMod b) { return a.n != b.n; }
	friend IntMod operator+(IntMod a, IntMod b) { return build(a.n >= MOD - b.n ? a.n - MOD + b.n : a.n + b.n); }
	friend IntMod operator-(IntMod a, IntMod b) { return build(a.n >= b.n ? a.n - b.n : a.n - b.n + MOD); }
	friend IntMod operator*(IntMod a, IntMod b) { return build(static_cast<base_type>(static_cast<long long>(a.n) * b.n % MOD)); }
	friend IntMod operator/(IntMod a, IntMod b) { return a * inverse(b); }
	friend IntMod pow(IntMod p, long long e)
	{
		if (e <= 0) return IntMod(1);
		IntMod r = IntMod(1);
		while (1) { if (e & 1) r *= p; e /= 2; if (e) p = p * p; else break; }
		return r;
	}

	friend istream& operator>>(istream &stream, IntMod &a) { stream >> a.n; return stream; }
	friend ostream& operator<<(ostream &stream, const IntMod &a) { stream << a.n; return stream; }
};
template<typename base_type, base_type _MOD> base_type IntMod<base_type, _MOD>::inverse_cache[INVERSE_CACHE_SIZE];
template<typename base_type, base_type _MOD> bool IntMod<base_type, _MOD>::inverse_cache_ready;
template<typename base_type, base_type _MOD> base_type IntMod<base_type, _MOD>::MOD = _MOD;

using Int= IntMod<int,1000000007>;

const int n=50;

Int f[n+4][n+4][n+4][n+4];

bool calc(int c1,int c2,int &d1,int &d2)
{
	while (c1>0 || c2>0)
	{
		if (c1>0 && d2>0)
		{
			int w=min(c1,d2);
			d1+=w; c1-=w; d2-=w;
			continue;
		}
		if (c2>0 && d1>0)
		{
			int w=min(c2,d1);
			d2+=w; c2-=w; d1-=w;
			continue;
		}
		return false;
	}
	return true;
}
void solve()
{
	Int p[n+4],inv_p[n+4];
	for (int i=0;i<=n;i++) p[i]=((i==0)?1:(p[i-1]*i));
	for (int i=0;i<=n;i++) inv_p[i]=1/p[i];
	memset(f,0,sizeof(f));
	f[n][0][0][0]=1;
	Int ret[n+4];
	for (int i=0;i<=n;i++) ret[i]=0;
	for (int d=n;d>=0;d--) REP(c1,n+1) REP(c2,n+1) REP(s,n+1) if (f[d][c1][c2][s].n)
	{
		//printf("%d %d %d %d  : %d\n",d,c1,c2,s,f[d][c1][c2][s].n);
		if (d==0)
		{
			if (c1==1 && c2==0) ret[s]+=f[d][c1][c2][s];
		}
		else
		{
			REP(d1,n+1) REP(d2,n+1) 
			{
				if (s+d1+d2>n) break;
				int e1=d1,e2=d2;
				if (!calc(c1,c2,e1,e2)) continue;
				f[d-1][e1][e2][s+d1+d2]+=f[d][c1][c2][s]*inv_p[d1]*inv_p[d2];
			}
		}
	}
	for (int i=1;i<=n;i++)
		printf("%d, \n",(ret[i]*p[i]).n);
}

int ret[]={1,
2,
12,
84,
770,
8340,
106400,
1546888,
25343766,
461133960,
232367169,
627905865,
632459808,
928262728,
919805769,
382796331,
887217496,
639768068,
869694124,
205875097,
205589953,
487772376,
239955313,
998339621,
31622834,
902930073,
146839084,
449786840,
982224660,
865803735,
21834818,
721531716,
26008837,
471774471,
69010090,
700009308,
776938882,
645550477,
526939604,
142728157,
654489641,
128201240,
185493259,
789721045,
977049419,
589149550,
700648836,
25087729,
874433491,
352791804};
int main()
{
#ifdef _MSC_VER
	//freopen("input.txt","r",stdin);
#endif
	std::ios::sync_with_stdio(false);
	int m;
	cin>>m;
	printf("%d\n",ret[m-1]);
	return 0;
}

