import java.util.ArrayList;
import java.util.List;

public class Euler270 {

    static class Point {
        int x, y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static List<Point> buildBoundary(int n) {
        List<Point> pts = new ArrayList<>();
        for (int x = 0; x <= n; x++)
            pts.add(new Point(x, 0));
        for (int y = 1; y <= n; y++)
            pts.add(new Point(n, y));
        for (int x = n - 1; x >= 0; x--)
            pts.add(new Point(x, n));
        for (int y = n - 1; y >= 1; y--)
            pts.add(new Point(0, y));
        return pts;
    }

    static boolean sameSide(Point a, Point b, int n) {
        if (a.y == 0 && b.y == 0)
            return true;
        if (a.y == n && b.y == n)
            return true;
        if (a.x == 0 && b.x == 0)
            return true;
        if (a.x == n && b.x == n)
            return true;
        return false;
    }

    static long countTriangulations(int n) {
        if (n <= 0)
            return 0;
        long kMod = 100000000L;
        List<Point> pts = buildBoundary(n);
        int m = pts.size();

        boolean[][] allowed = new boolean[m][m];
        for (int i = 0; i < m; i++) {
            for (int j = i + 1; j < m; j++) {
                boolean ok = false;
                if (j == i + 1 || (i == 0 && j == m - 1)) {
                    ok = true;
                } else if (!sameSide(pts.get(i), pts.get(j), n)) {
                    ok = true;
                }
                allowed[i][j] = ok;
                allowed[j][i] = ok;
            }
        }

        long[][] dp = new long[m][m];
        for (int i = 0; i < m - 1; i++) {
            dp[i][i + 1] = 1;
        }

        for (int length = 2; length < m; length++) {
            for (int i = 0; i < m - length; i++) {
                int j = i + length;
                if (!allowed[i][j]) {
                    dp[i][j] = 0;
                    continue;
                }
                long s = 0;
                for (int k = i + 1; k < j; k++) {
                    long left = dp[i][k];
                    if (left == 0)
                        continue;
                    long right = dp[k][j];
                    if (right == 0)
                        continue;
                    s = (s + left * right) % kMod;
                }
                dp[i][j] = s;
            }
        }
        return dp[0][m - 1];
    }

    public static void main(String[] args) {
        System.out.println(countTriangulations(30));
    }
}