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

public class Euler1003 {
    private static final int TARGET_K = 80;
    private static final int TASK_PREFIX = 24;
    private static final int NEG_INF = -1_000_000_000;
    private static final long EMPTY = Long.MIN_VALUE;

    private static final class Options {
        int targetK = TARGET_K;
        boolean runCheckpoints = true;
    }

    private static final class Power {
        final long constant;
        final long coeff;

        Power(long constant, long coeff) {
            this.constant = constant;
            this.coeff = coeff;
        }
    }

    private static final class LeftTask {
        final int pos;
        final int last;
        final long constant;
        final long coeff;

        LeftTask(int pos, int last, long constant, long coeff) {
            this.pos = pos;
            this.last = last;
            this.constant = constant;
            this.coeff = coeff;
        }
    }

    private static final class LongLongMap {
        private final long[] keys;
        private final long[] values;
        private final int mask;

        LongLongMap(int expectedSize) {
            int capacity = 1;
            while (capacity < Math.max(4, expectedSize * 2)) {
                capacity <<= 1;
            }
            keys = new long[capacity];
            values = new long[capacity];
            Arrays.fill(keys, EMPTY);
            mask = capacity - 1;
        }

        private static long mix(long x) {
            x ^= x >>> 33;
            x *= 0xff51afd7ed558ccdL;
            x ^= x >>> 33;
            x *= 0xc4ceb9fe1a85ec53L;
            x ^= x >>> 33;
            return x;
        }

        void put(long key, long value) {
            if (key == EMPTY) {
                throw new IllegalArgumentException("reserved key");
            }
            int slot = (int) mix(key) & mask;
            while (keys[slot] != EMPTY) {
                if (keys[slot] == key) {
                    throw new IllegalStateException("unexpected duplicate right-side coefficient");
                }
                slot = (slot + 1) & mask;
            }
            keys[slot] = key;
            values[slot] = value;
        }

        long get(long key) {
            int slot = (int) mix(key) & mask;
            while (keys[slot] != EMPTY) {
                if (keys[slot] == key) {
                    return values[slot];
                }
                slot = (slot + 1) & mask;
            }
            return EMPTY;
        }
    }

    private static final class RightBucket {
        private long[] coeffs = new long[1024];
        private long[] constants = new long[1024];
        private int size = 0;

        void add(long coeff, long constant) {
            if (size == coeffs.length) {
                int next = coeffs.length << 1;
                coeffs = Arrays.copyOf(coeffs, next);
                constants = Arrays.copyOf(constants, next);
            }
            coeffs[size] = coeff;
            constants[size] = constant;
            size++;
        }

        LongLongMap finish() {
            LongLongMap map = new LongLongMap(size);
            for (int i = 0; i < size; ++i) {
                map.put(coeffs[i], constants[i]);
            }
            coeffs = null;
            constants = null;
            return map;
        }
    }

    private static Power[] buildPowers(int k) {
        Power[] powers = new Power[Math.max(2, k)];
        powers[0] = new Power(1, 0);
        powers[1] = new Power(0, 1);
        for (int i = 2; i < k; ++i) {
            Power prev = powers[i - 1];
            powers[i] = new Power(-2L * prev.coeff, prev.constant - prev.coeff);
        }
        return Arrays.copyOf(powers, k);
    }

    private static long[] evaluatePositions(int[] positions, Power[] powers) {
        long constant = 0;
        long coeff = 0;
        for (int pos : positions) {
            constant += powers[pos].constant;
            coeff += powers[pos].coeff;
        }
        return new long[]{constant, coeff};
    }

    private static List<Integer> singletonPositions(long n, int limit) {
        long[] stones = new long[limit + 4];
        List<Integer> positions = new ArrayList<>();
        stones[0] = n;
        for (int i = 0; i < limit; ++i) {
            if ((stones[i] & 1L) != 0) {
                positions.add(i);
            }
            long moved = stones[i] / 2;
            stones[i + 1] += moved;
            stones[i + 3] += moved;
        }
        return positions;
    }

    private static int leftCategory(int last, int mid) {
        if (last < 0 || last <= mid - 3) {
            return 0;
        }
        if (last == mid - 2) {
            return 1;
        }
        return 2;
    }

    private static int rightCategory(int first, int mid) {
        if (first < 0 || first >= mid + 2) {
            return 0;
        }
        if (first == mid + 1) {
            return 1;
        }
        return 2;
    }

    private static boolean compatibleBoundary(int leftCat, int rightCat) {
        if (leftCat == 0) {
            return true;
        }
        if (leftCat == 1) {
            return rightCat != 2;
        }
        return rightCat == 0;
    }

    private static void enumerateRight(
            int pos,
            int end,
            int mid,
            int last,
            int first,
            long constant,
            long coeff,
            Power[] powers,
            RightBucket[] buckets) {
        if (pos == end) {
            buckets[rightCategory(first, mid)].add(coeff, constant);
            return;
        }

        enumerateRight(pos + 1, end, mid, last, first, constant, coeff, powers, buckets);

        if (last < 0 || pos - last >= 3) {
            Power power = powers[pos];
            int nextFirst = first < 0 ? pos : first;
            enumerateRight(
                    pos + 1,
                    end,
                    mid,
                    pos,
                    nextFirst,
                    constant + power.constant,
                    coeff + power.coeff,
                    powers,
                    buckets);
        }
    }

    private static void buildLeftTasks(
            int pos,
            int stop,
            int last,
            long constant,
            long coeff,
            Power[] powers,
            List<LeftTask> tasks) {
        if (pos == stop) {
            tasks.add(new LeftTask(pos, last, constant, coeff));
            return;
        }

        buildLeftTasks(pos + 1, stop, last, constant, coeff, powers, tasks);

        if (last < 0 || pos - last >= 3) {
            Power power = powers[pos];
            buildLeftTasks(
                    pos + 1,
                    stop,
                    pos,
                    constant + power.constant,
                    coeff + power.coeff,
                    powers,
                    tasks);
        }
    }

    private static long queryTable(LongLongMap table, long targetCoeff, long leftConstant) {
        long rightConstant = table.get(targetCoeff);
        if (rightConstant == EMPTY) {
            return 0;
        }
        long value = leftConstant + rightConstant;
        return value > 0 ? value : 0;
    }

    private static long addMatches(
            int leftCat,
            long leftCoeff,
            long leftConstant,
            LongLongMap[] tables) {
        long total = 0;
        long targetCoeff = -leftCoeff;
        for (int rightCat = 0; rightCat < 3; ++rightCat) {
            if (compatibleBoundary(leftCat, rightCat)) {
                total += queryTable(tables[rightCat], targetCoeff, leftConstant);
            }
        }
        return total;
    }

    private static long combineLeftDfs(
            int pos,
            int mid,
            int last,
            long constant,
            long coeff,
            Power[] powers,
            LongLongMap[] tables) {
        if (pos == mid) {
            return addMatches(leftCategory(last, mid), coeff, constant, tables);
        }

        long total = combineLeftDfs(pos + 1, mid, last, constant, coeff, powers, tables);
        if (last < 0 || pos - last >= 3) {
            Power power = powers[pos];
            total += combineLeftDfs(
                    pos + 1,
                    mid,
                    pos,
                    constant + power.constant,
                    coeff + power.coeff,
                    powers,
                    tables);
        }
        return total;
    }

    private static long solveS(int k) {
        if (k == 0) {
            return 0;
        }

        int mid = k / 2;
        Power[] powers = buildPowers(k);

        RightBucket[] rightBuckets = {new RightBucket(), new RightBucket(), new RightBucket()};
        enumerateRight(mid, k, mid, NEG_INF, -1, 0, 0, powers, rightBuckets);

        LongLongMap[] tables = new LongLongMap[3];
        for (int i = 0; i < 3; ++i) {
            tables[i] = rightBuckets[i].finish();
            rightBuckets[i] = null;
        }

        int taskStop = Math.min(mid, TASK_PREFIX);
        List<LeftTask> tasks = new ArrayList<>();
        buildLeftTasks(0, taskStop, NEG_INF, 0, 0, powers, tasks);

        long total = 0;
        for (LeftTask task : tasks) {
            total += combineLeftDfs(
                    task.pos,
                    mid,
                    task.last,
                    task.constant,
                    task.coeff,
                    powers,
                    tables);
        }
        return total;
    }

    private static void check(boolean ok, String message) {
        if (!ok) {
            throw new IllegalStateException("Checkpoint failed: " + message);
        }
    }

    private static void runCheckpoints() {
        Power[] powers = buildPowers(TARGET_K);

        int[] p68 = {2, 5, 8, 13};
        int[] p90 = {1, 13};
        check(Arrays.equals(evaluatePositions(new int[]{0}, powers), new long[]{1, 0}), "n=1 polynomial");
        check(Arrays.equals(evaluatePositions(p68, powers), new long[]{68, 0}), "n=68 polynomial");
        check(Arrays.equals(evaluatePositions(p90, powers), new long[]{90, 0}), "n=90 polynomial");

        check(singletonPositions(1, 40).equals(List.of(0)), "n=1 trace");
        check(singletonPositions(68, 50).equals(List.of(2, 5, 8, 13)), "n=68 trace");
        check(singletonPositions(90, 50).equals(List.of(1, 13)), "n=90 trace");

        check(solveS(14) == 159, "S(14)");
        check(solveS(30) == 33438, "S(30)");

        System.err.println("Validation checkpoints passed.");
    }

    private static void usage() {
        System.err.println("Usage:");
        System.err.println("  java Euler1003 [k] [--skip-checkpoints] [--single-thread] [--threads=N]");
    }

    private static Options parseOptions(String[] args) {
        Options options = new Options();
        for (String arg : args) {
            if (arg.equals("--skip-checkpoints")) {
                options.runCheckpoints = false;
            } else if (arg.equals("--single-thread") || arg.startsWith("--threads=")) {
                // Accepted for command-line compatibility with the C++ version.
            } else if (arg.startsWith("-")) {
                usage();
                System.exit(1);
            } else {
                options.targetK = Integer.parseInt(arg);
            }
        }
        if (options.targetK < 0 || options.targetK > TARGET_K) {
            throw new IllegalArgumentException("k must satisfy 0 <= k <= " + TARGET_K + ".");
        }
        return options;
    }

    public static void main(String[] args) {
        Options options = parseOptions(args);
        if (options.runCheckpoints) {
            runCheckpoints();
        }
        System.out.println(solveS(options.targetK));
    }
}