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>
// #pragma GCC optimize ("O3")
// #pragma GCC target ("sse4")
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;

#define REP(i,n) for(int i=0;i<(n);++i)
#define FOR(i,a,b) for (int i=(a); i<(b); ++i)
#define FORD(i,a,b) for (int i=(a)-1; i>=(b); --i)

#define pb push_back
#define mp make_pair
#define st first
#define nd second

const int MOD = 1000000007;

LL SN[55][55];

LL choose(int N, int K1, int K2) {
  if (N < K1 + K2) return 0;
  return SN[N][K1] * SN[N-K1][K2] % MOD;
}

LL DP[55][55][55];

int main() {
  // ios_base::sync_with_stdio(0);

    int N;
    scanf("%d", &N);

  REP(i,55) {
    SN[i][0] = SN[i][i] = 1;
    FOR(j,1,i) SN[i][j] = (SN[i-1][j-1] + SN[i-1][j]) % MOD;
  }

  DP[1][1][0] = 1;
  FOR(i,2,51) {
    for (int pos = 0; pos <= i; ++pos) {
      for (int neg = 0; pos + neg <= i; ++neg) {
        int left = i - pos - neg;
        for (int prev_pos = 0; prev_pos <= left; ++prev_pos)
          for (int prev_neg = 0; prev_pos+prev_neg <= left; ++prev_neg) {
            int up_pos = prev_pos - pos + neg;
            int up_neg = prev_neg - neg + pos;

            if (up_pos < 0 || up_neg < 0) continue;
            if (pos > neg && prev_pos < pos - neg) continue;
            if (neg > pos && prev_neg < neg - pos) continue;

            (DP[i][pos][neg] += DP[left][prev_pos][prev_neg] * choose(left, up_pos, up_neg)) %= MOD;
          }
      }
    }
  }

  LL result = 0;
  REP(pos,51)REP(neg,51) (result += DP[N][pos][neg] * choose(N,pos,neg)) %= MOD;
  printf("%lld\n", result);
}
