public class Euler215 {
    public static void main(String[] args) {
        int width = 32, height = 10;
        java.util.List<Integer> rows = new java.util.ArrayList<>();
        genRows(0, 0, width, rows);
        int n = rows.size();
        int[][] compatible = new int[n][];
        for (int i = 0; i < n; i++) {
            java.util.List<Integer> comp = new java.util.ArrayList<>();
            for (int j = 0; j < n; j++)
                if ((rows.get(i) & rows.get(j)) == 0)
                    comp.add(j);
            compatible[i] = comp.stream().mapToInt(Integer::intValue).toArray();
        }
        long[] dp = new long[n];
        java.util.Arrays.fill(dp, 1L);
        for (int h = 1; h < height; h++) {
            long[] next = new long[n];
            for (int i = 0; i < n; i++) {
                long s = 0;
                for (int j : compatible[i])
                    s += dp[j];
                next[i] = s;
            }
            dp = next;
        }
        long total = 0;
        for (long v : dp)
            total += v;
        System.out.println(total);
    }

    static void genRows(int pos, int mask, int width, java.util.List<Integer> rows) {
        if (pos == width) {
            rows.add(mask);
            return;
        }
        for (int brick : new int[] { 2, 3 }) {
            int nxt = pos + brick;
            if (nxt > width)
                continue;
            int nmask = mask;
            if (nxt < width)
                nmask |= (1 << nxt);
            genRows(nxt, nmask, width, rows);
        }
    }
}