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>

using namespace std;

typedef long long ll;

const int MOD = 1e9 + 7; // change if needed

struct Modint {
  ll val;
  
  Modint (ll _val = 0)
    : val(_val % MOD) {}

  Modint operator+ (Modint other) const {
    return Modint(val + other.val);
  }

  void operator+= (Modint other) {
    val += other.val;
    val %= MOD;
  }

  Modint operator- () const {
    return Modint(MOD - val);
  }

  Modint operator- (Modint other) const {
    return Modint(val + MOD - other.val);
  }

  void operator-= (Modint other) {
    val += MOD - other.val;
    val %= MOD;
  }

  Modint operator* (Modint other) const {
    return Modint(val * other.val);
  }

  void operator*= (Modint other) {
    val *= other.val;
    val %= MOD;
  }

  bool operator== (Modint other) const {
    return val == other.val;
  }

  bool operator!= (Modint other) const {
    return val != other.val;
  }
};

Modint exp (Modint a, int k) {
  if (k == 0) {
    return Modint(1);
  } else if (k % 2 == 0) {
    Modint half = exp(a, k / 2);
    return half * half;
  } else {
    return a * exp(a, k - 1);
  }
}

Modint inv (Modint a) {
  return exp(a, MOD - 2);
}

ostream& operator<< (ostream& out, Modint p) {
  out << p.val;
  return out;
}


const int MAX_N = 55;

Modint choose [MAX_N][MAX_N];
Modint dp [MAX_N][MAX_N][MAX_N][MAX_N];

int main () {
  choose[0][0] = Modint(1);
  for (int i = 1; i < MAX_N; i++) {
    choose[i][0] = Modint(1);
    for (int j = 1; j < MAX_N; j++) {
      choose[i][j] = choose[i - 1][j - 1] + choose[i - 1][j];
    }
  }
  
  int n;
  cin >> n;

  if (n == 1) {
    cout << 1 << endl;
    return 0;
  }
  
  dp[0][1][0][n] = Modint(1);
  for (int t = 0; t < n; t++) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; i + j <= n; j++) {
        for (int l = i + j; l <= n; l++) {
          if (dp[t][i][j][l] == Modint(0)) continue;
          // cerr << t << " " << i << " " << j << " " << l << ": " << dp[t][i][j][l] << endl;
          for (int ni = 0; ni < n; ni++) {
            for (int k = 0; k <= i + j; k++) {
              int kp = i + j - k;
              int dnj = 2 * ni - i + j + k - kp;
              if (dnj % 2 != 0) continue;
              int nj = dnj / 2;
              if (i == 0 && j == 0 && ni + nj > 0) continue;
              if (nj < 0 || n <= nj || l - i - j < ni + nj) continue;
              dp[t + 1][ni][nj][l - i - j] += dp[t][i][j][l] * choose[l][k] * choose[l - k][kp];
              /*
              if (t + 1 == 2 && ni == 1 && nj == 1 && l - i - j == 2) {
                cerr << " " << t << " " << i << " " << j << " " << l << " " << k << " "
                     << kp << ": " << dp[t][i][j][l] * choose[l][k] * choose[l - k][kp] << endl; 
              }
              */
              //cerr << t + 1 << " " << ni << " " << nj << " " << l - i - j << endl;
            }
          }
        }
      }
    }
  }

  cout << dp[n][0][0][0] << endl;
}
