import java.math.BigInteger;

public class Euler948 {

    static BigInteger binom(long n, long k) {
        if (k > n) {
            return BigInteger.ZERO;
        }
        if (k > n - k) {
            k = n - k;
        }

        BigInteger result = BigInteger.ONE;
        for (long i = 1; i <= k; ++i) {
            result = result.multiply(BigInteger.valueOf(n - k + i)).divide(BigInteger.valueOf(i));
        }
        return result;
    }

    static BigInteger catalan(long k) {
        return binom(2 * k, k).divide(BigInteger.valueOf(k + 1));
    }

    static BigInteger pow2(long n) {
        return BigInteger.ONE.shiftLeft((int) n);
    }

    static BigInteger F_formula(long n) {
        if (n % 2 == 1) {
            long k = (n - 1) / 2;
            return pow2(n).subtract(binom(2 * k, k).multiply(BigInteger.valueOf(2)));
        }

        long k = n / 2;
        return pow2(n)
                .subtract(binom(2 * k - 1, k - 1).multiply(BigInteger.valueOf(2)))
                .subtract(catalan(k - 1));
    }

    static boolean bitIsR(long mask, int i) {
        return ((mask >> i) & 1L) != 0L;
    }

    static long F_bruteforce(int n) {
        long count = 0;
        long total = 1L << n;

        for (long mask = 0; mask < total; ++mask) {
            byte[][] wl = new byte[n][n];
            byte[][] wr = new byte[n][n];

            for (int i = 0; i < n; ++i) {
                boolean r = bitIsR(mask, i);
                wl[i][i] = (byte) (!r ? 1 : 0);
                wr[i][i] = (byte) (r ? 1 : 0);
            }

            for (int len = 2; len <= n; ++len) {
                for (int i = 0; i + len - 1 < n; ++i) {
                    int j = i + len - 1;

                    byte leftWin = 0;
                    for (int t = i + 1; t <= j; ++t) {
                        if (wr[t][j] == 0) {
                            leftWin = 1;
                            break;
                        }
                    }
                    wl[i][j] = leftWin;

                    byte rightWin = 0;
                    for (int t = i; t < j; ++t) {
                        if (wl[i][t] == 0) {
                            rightWin = 1;
                            break;
                        }
                    }
                    wr[i][j] = rightWin;
                }
            }

            if (wl[0][n - 1] == 1 && wr[0][n - 1] == 1) {
                ++count;
            }
        }

        return count;
    }

    public static String solve() {
        return F_formula(60).toString();
    }

    public static void main(String[] args) {
        if (!F_formula(3).equals(BigInteger.valueOf(4)) || !F_formula(8).equals(BigInteger.valueOf(181))) {
            System.out.println("Validation failed");
            return;
        }

        for (int n = 1; n <= 12; ++n) {
            if (!F_formula((long) n).equals(BigInteger.valueOf(F_bruteforce(n)))) {
                System.out.println("Validation failed for n = " + n);
                return;
            }
        }

        System.out.println(solve());
    }
}