import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Euler473 {

    static class LowState {
        long b, a;
        int last;

        LowState(long b, long a, int last) {
            this.b = b;
            this.a = a;
            this.last = last;
        }
    }

    static class HighState {
        long b, a;
        int first;

        HighState(long b, long a, int first) {
            this.b = b;
            this.a = a;
            this.first = first;
        }
    }

    static class Bucket {
        List<Long> values = new ArrayList<>();
        long[] pref;
    }

    private static long[] buildFib() {
        long[] f = new long[100];
        f[0] = 0;
        f[1] = 1;
        for (int i = 2; i < 100; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f;
    }

    private static void buildPairCoefficients(long[] fib, long[] coeffA, long[] coeffB, int maxIndex) {
        for (int i = 0; i <= maxIndex; i++) {
            long posA = 0;
            long posB = 0;
            if (i == 0) {
                posA = 1;
                posB = 0;
            } else {
                posA = fib[i - 1];
                posB = fib[i];
            }

            int m = i + 1;
            long sign = (m % 2 == 0) ? 1 : -1;
            long negA = sign * fib[m + 1];
            long negB = -sign * fib[m];

            coeffA[i] = posA + negA;
            coeffB[i] = posB + negB;
        }
    }

    private static long[] minMaxPossibleA(int n, long[] coeffA) {
        long kInf = 1L << 61;
        long[][] minDp = new long[n + 1][2];
        long[][] maxDp = new long[n + 1][2];

        for (int i = 0; i <= n; i++) {
            minDp[i][0] = kInf;
            minDp[i][1] = kInf;
            maxDp[i][0] = -kInf;
            maxDp[i][1] = -kInf;
        }
        minDp[n][0] = 0;
        minDp[n][1] = 0;
        maxDp[n][0] = 0;
        maxDp[n][1] = 0;

        for (int idx = n - 1; idx >= 0; idx--) {
            for (int prev = 0; prev <= 1; prev++) {
                long bestMin = kInf;
                long bestMax = -kInf;

                for (int bit = 0; bit <= 1; bit++) {
                    if (idx == 0 && bit == 1)
                        continue;
                    if (idx == n - 1 && bit == 0)
                        continue;
                    if (prev == 1 && bit == 1)
                        continue;

                    long add = (bit == 1) ? coeffA[idx] : 0;
                    long childMin = minDp[idx + 1][bit];
                    long childMax = maxDp[idx + 1][bit];

                    if (childMin >= kInf / 2 || childMax <= -kInf / 2)
                        continue;

                    bestMin = Math.min(bestMin, add + childMin);
                    bestMax = Math.max(bestMax, add + childMax);
                }

                minDp[idx][prev] = bestMin;
                maxDp[idx][prev] = bestMax;
            }
        }
        return new long[] { minDp[0][0], maxDp[0][0] };
    }

    private static void dfsLow(int idx, int prev, long sumB, long sumA, int last, int end, long[] coeffA, long[] coeffB,
            List<LowState> out) {
        if (idx > end) {
            out.add(new LowState(sumB, sumA, last));
            return;
        }
        if (idx == 0) {
            dfsLow(1, 0, sumB, sumA, 0, end, coeffA, coeffB, out);
            return;
        }

        dfsLow(idx + 1, 0, sumB, sumA, 0, end, coeffA, coeffB, out);

        if (prev == 0) {
            dfsLow(idx + 1, 1, sumB + coeffB[idx], sumA + coeffA[idx], 1, end, coeffA, coeffB, out);
        }
    }

    private static void dfsHigh(int idx, int prev, long sumB, long sumA, int first, int start, int end, long[] coeffA,
            long[] coeffB, List<HighState> out) {
        if (idx > end) {
            out.add(new HighState(sumB, sumA, first));
            return;
        }

        if (idx == end) {
            if (prev == 1)
                return;
            dfsHigh(idx + 1, 1, sumB + coeffB[idx], sumA + coeffA[idx], idx == start ? 1 : first, start, end, coeffA,
                    coeffB, out);
            return;
        }

        dfsHigh(idx + 1, 0, sumB, sumA, idx == start ? 0 : first, start, end, coeffA, coeffB, out);

        if (prev == 0) {
            dfsHigh(idx + 1, 1, sumB + coeffB[idx], sumA + coeffA[idx], idx == start ? 1 : first, start, end, coeffA,
                    coeffB, out);
        }
    }

    private static long solveSum(long limit) {
        int maxIndex = 64;
        long[] fib = buildFib();
        long[] coeffA = new long[maxIndex + 1];
        long[] coeffB = new long[maxIndex + 1];
        buildPairCoefficients(fib, coeffA, coeffB, maxIndex);

        long total = 1;

        for (int n = 2; n <= 64; n++) {
            long[] minMax = minMaxPossibleA(n, coeffA);
            long minA = minMax[0];
            long maxA = minMax[1];

            if (maxA < 1 || minA > limit)
                continue;

            int mid = n / 2;
            List<LowState> lowStates = new ArrayList<>();
            if (mid - 1 < 0) {
                lowStates.add(new LowState(0, 0, 0));
            } else {
                dfsLow(0, 0, 0, 0, 0, mid - 1, coeffA, coeffB, lowStates);
            }

            List<HighState> highStates = new ArrayList<>();
            if (mid > n - 1) {
                highStates.add(new HighState(0, 0, 0));
            } else {
                dfsHigh(mid, 0, 0, 0, 0, mid, n - 1, coeffA, coeffB, highStates);
            }

            Map<Long, Bucket>[] highMaps = new Map[] { new HashMap<>(), new HashMap<>() };

            for (HighState st : highStates) {
                if (!highMaps[st.first].containsKey(st.b)) {
                    highMaps[st.first].put(st.b, new Bucket());
                }
                highMaps[st.first].get(st.b).values.add(st.a);
            }

            for (int fb = 0; fb <= 1; fb++) {
                for (Bucket bucket : highMaps[fb].values()) {
                    Collections.sort(bucket.values);
                    bucket.pref = new long[bucket.values.size() + 1];
                    for (int i = 0; i < bucket.values.size(); i++) {
                        bucket.pref[i + 1] = bucket.pref[i] + bucket.values.get(i);
                    }
                }
            }

            for (LowState st : lowStates) {
                for (int fb = 0; fb <= 1; fb++) {
                    if (st.last == 1 && fb == 1)
                        continue;
                    long targetB = -st.b;
                    if (!highMaps[fb].containsKey(targetB))
                        continue;

                    Bucket bucket = highMaps[fb].get(targetB);
                    List<Long> pop = bucket.values;
                    long lowNeeded = 1 - st.a;
                    long highNeeded = limit - st.a;

                    int lo = lowerBound(pop, lowNeeded);
                    int hi = upperBound(pop, highNeeded);

                    if (lo == hi)
                        continue;

                    long count = hi - lo;
                    long sumHigh = bucket.pref[hi] - bucket.pref[lo];
                    total += count * st.a + sumHigh;
                }
            }
        }

        return total;
    }

    private static int lowerBound(List<Long> arr, long target) {
        int low = 0, high = arr.size();
        while (low < high) {
            int mid = (low + high) >>> 1;
            if (arr.get(mid) < target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }

    private static int upperBound(List<Long> arr, long target) {
        int low = 0, high = arr.size();
        while (low < high) {
            int mid = (low + high) >>> 1;
            if (arr.get(mid) <= target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }

    public static void main(String[] args) {
        long limit = 10_000_000_000L;
        long ans = solveSum(limit);
        System.out.println(ans);
    }
}