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;
#define rep(i,a,b) for (int i = (a); i <= (b); ++ i)
#define rrp(i,a,b) for (int i = (a); i >= (b); -- i)
#define gc() getchar()
#define fir first
#define sec second
typedef pair<int,int> pii;
typedef double db;
typedef long long ll;
template <typename tp>
inline void read(tp& x) {
  x = 0; char tmp; bool key = 0;
  for (tmp = gc(); !isdigit(tmp); tmp = gc())
    key = (tmp == '-');
  for (; isdigit(tmp); tmp = gc())
    x = (x << 3) + (x << 1) + (tmp ^ '0');
  if (key) x = -x;
}
template <typename tp>
inline void ckmn(tp& x,tp y) {
  x = x < y ? x : y;
}
template <typename tp>
inline void ckmx(tp& x,tp y) {
  x = x < y ? y : x;
}

const int N = 55, MOD = (int)(1e9 + 7);
inline void Add(int &x,int y) {
  x = x + y >= MOD ? x + y - MOD : x + y;
}
inline void Sub(int& x,int y) {
  x = x - y < 0 ? x - y + MOD : x - y;
}
int power(int a,int b) {
  int ret = 1;
  while (b) {
    if (b&1) ret = 1ll * ret * a % MOD;
    a = 1ll * a * a % MOD;
    b >>= 1;
  }
  return ret;
}

int dp[2][2][N][N], jc[N], ijc[N];
int n, ans;
int main() {
  read(n);
  jc[0] = 1;
  rep (i, 1, n) jc[i] = 1ll * i * jc[i-1] % MOD;
  ijc[n] = power(jc[n], MOD - 2);
  rrp (i, n-1, 0) ijc[i] = 1ll * ijc[i+1] * (i+1) % MOD;
  dp[0][0][1][0] = 1;
  for (int i = 1, j = 1; i <= n; ++ i, j ^= 1) {
    memset(dp[j], 0, sizeof dp[j]);
    rep (tp, 0, 1) rep (a, 0, n) rep (b, 0, n) if (dp[j^1][tp][a][b]) {
      int n0 = 0, n1 = 0;
      if (tp == 0) n0 += a;
      else n1 += a;
      rep (c, 0, n) rep (d, 0, n - b - c) if (c + d > 0) {
	int tmp = c + d - n0 - n1;
	if (i == 1 && c + d > 1) continue;
	if ((tmp&1) || tmp < 0) continue;
	tmp >>= 1;
	int nn0 = n0 + tmp;
	int nn1 = n1 + tmp;
	if (d >= nn1)
	  Add(dp[j][0][d - nn1][b + c + d], 1ll * dp[j^1][tp][a][b] * ijc[c] % MOD * ijc[d] % MOD);
	else
	  Add(dp[j][1][c - nn0][b + c + d], 1ll * dp[j^1][tp][a][b] * ijc[c] % MOD * ijc[d] % MOD);
      }
    }
    Add(ans, dp[j][0][0][n]);
  }
  ans = 1ll * ans * jc[n] % MOD;
  cout << ans << endl;
  return 0;
}
