import java.util.HashMap;
import java.util.Map;

public class Euler400 {
    static final long K_MOD = 1000000000000000000L;

    static class Solver400Impl {
        int n;
        int[] sg;
        Map<Integer, Long>[] cache;

        @SuppressWarnings("unchecked")
        Solver400Impl(int n) {
            this.n = n;
            this.sg = new int[n + 1];
            this.cache = new Map[n + 1];

            for (int i = 0; i <= n; i++) {
                this.cache[i] = new HashMap<>();
            }

            if (n >= 1)
                sg[1] = 0;
            if (n >= 2)
                sg[2] = 1;

            for (int i = 3; i <= n; i++) {
                sg[i] = (1 + sg[i - 1]) ^ (1 + sg[i - 2]);
            }
        }

        long prune(int treeSize, int target) {
            if (target == -1)
                return 1;
            if (target < -1)
                return 0;
            if (treeSize == 1)
                return 0;
            if (treeSize == 2)
                return target == 0 ? 1 : 0;

            Map<Integer, Long> memo = cache[treeSize];
            Long cached = memo.get(target);
            if (cached != null) {
                return cached;
            }

            int rightTarget = ((sg[treeSize - 1] + 1) ^ target) - 1;
            int leftTarget = ((sg[treeSize - 2] + 1) ^ target) - 1;

            long right = prune(treeSize - 2, rightTarget);
            long left = prune(treeSize - 1, leftTarget);

            long res = right + left;
            if (res >= K_MOD)
                res -= K_MOD;

            memo.put(target, res);
            return res;
        }
    }

    static String solve() {
        int k = 10000;
        Solver400Impl solver = new Solver400Impl(k);
        long ans = solver.prune(k, 0);
        return String.format("%018d", ans);
    }

    public static void main(String[] args) throws InterruptedException {
        String[] result = new String[1];
        Thread t = new Thread(null, () -> {
            result[0] = solve();
        }, "Solver", 1 << 26);
        t.start();
        t.join();
        System.out.println(result[0]);
    }
}