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;

#define MOD 1000000007
LL powmod(LL a, LL n){
    if(n == 0) return 1;
    if(n % 2) return (a*powmod(a,n-1)) % MOD;
    LL c = powmod(a, n/2);
    return (c*c) % MOD;
}
LL inv(LL a){
    return powmod(a, MOD-2);
}
LL fact[110000];
LL invfact[110000];

LL ncr(LL n, LL r){
    if(r < 0 || n < 0) return 0;
    if(n < r) return 0;
    LL a = fact[n];
    a = (a * invfact[r]) % MOD;
    a = (a * invfact[n-r]) % MOD;
    return a;
}
void init(){
    fact[0] = 1;
    invfact[0] = 1;
    LL inv2 = inv(2);
    for(LL i = 1; i < 110000; i++){
        fact[i] = (i*fact[i-1]) % MOD;
        invfact[i] = inv(fact[i]);
    }
}

LL dp[51][51][51];

int main(){
    init();
    int N = 50;
    for(int button = 0; button <= N; button++){
        for(int i = 0; i <= N; i++){
            for(int j = 0; j <= N; j++){
                //calculate dp[i][j][button];
                dp[i][j][button] = 0;
                if(i == 0 && j == 0){
                    if(button == 0){
                        dp[i][j][button] = 1;
                    }
                    continue;
                }
                for(int c = 0; c <= button - i - j; c++){
                    for(int d = 0; c + d <= button - i - j; d++){
                        int a = i-c+d;
                        int b = j-d+c;
                        if(a < 0 || b < 0 || a > N || b > N) continue;
                        LL newans = dp[c][d][button - i - j];
                        newans = (newans * invfact[a]) % MOD;
                        newans = (newans * invfact[b]) % MOD;
                        dp[i][j][button] += newans;
                        dp[i][j][button] %= MOD;
                    }
                }
            }
        }
    }
    int n;
    cin >> n;
    cout << (dp[1][0][n] * fact[n]) % MOD << endl;
}
