import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

public class Euler366 {
    static final long kLimit = 1000000000000000000L;
    static final long kMod = 100000000L;

    static BigInteger tri(long n) {
        return BigInteger.valueOf(n).multiply(BigInteger.valueOf(n + 1)).divide(BigInteger.valueOf(2));
    }

    static BigInteger sumRange(long a, long b) {
        if (b < a)
            return BigInteger.ZERO;
        long len = b - a + 1;
        return BigInteger.valueOf(a + b).multiply(BigInteger.valueOf(len)).divide(BigInteger.valueOf(2));
    }

    static class Precomputed {
        List<Long> fib;
        long[] prefixLen;
        BigInteger[] tailSum;
        BigInteger[] intervalSum;
        BigInteger[] intervalPrefixSum;

        Precomputed(long maxN) {
            fib = new ArrayList<>();
            fib.add(1L);
            fib.add(1L);
            fib.add(2L);
            while (fib.get(fib.size() - 1) <= maxN) {
                int sz = fib.size();
                fib.add(fib.get(sz - 1) + fib.get(sz - 2));
            }

            int kmax = fib.size() - 2;
            int size = fib.size();

            prefixLen = new long[size];
            tailSum = new BigInteger[size];
            intervalSum = new BigInteger[size];
            intervalPrefixSum = new BigInteger[size];

            for (int i = 0; i < size; i++) {
                tailSum[i] = BigInteger.ZERO;
                intervalSum[i] = BigInteger.ZERO;
                intervalPrefixSum[i] = BigInteger.ZERO;
            }

            prefixLen[1] = 1;
            if (size > 2)
                prefixLen[2] = 1;
            if (size > 3)
                prefixLen[3] = 2;
            if (size > 4)
                prefixLen[4] = 3;
            if (size > 5)
                prefixLen[5] = 4;

            for (int k = 6; k <= kmax; k++) {
                prefixLen[k] = fib.get(k - 2) + prefixLen[k - 3];
            }

            if (size > 5)
                tailSum[5] = BigInteger.valueOf(1);
            if (size > 6)
                tailSum[6] = BigInteger.valueOf(2);

            for (int k = 7; k <= kmax; k++) {
                long a = prefixLen[k - 3];
                long b = prefixLen[k - 2] - 1;
                tailSum[k] = tailSum[k - 2].add(sumRange(a, b));
            }

            intervalSum[1] = BigInteger.ZERO;
            if (size > 2)
                intervalSum[2] = BigInteger.ZERO;

            for (int k = 3; k <= kmax; k++) {
                long p = prefixLen[k];
                intervalSum[k] = tri(p - 1).add(tailSum[k]);
            }

            for (int k = 1; k <= kmax; k++) {
                intervalPrefixSum[k] = intervalPrefixSum[k - 1].add(intervalSum[k]);
            }
        }
    }

    static BigInteger prefixTail(Precomputed data, int k, long j) {
        if (j < 0)
            return BigInteger.ZERO;
        if (k <= 4)
            return BigInteger.ZERO;
        if (k == 5)
            return BigInteger.ONE;
        if (k == 6)
            return BigInteger.valueOf(2);

        long start = data.prefixLen[k - 3];
        long end = data.prefixLen[k - 2] - 1;
        long blockLen = end - start + 1;

        if (j < blockLen) {
            return sumRange(start, start + j);
        }
        return sumRange(start, end).add(prefixTail(data, k - 2, j - blockLen));
    }

    static BigInteger prefixInterval(Precomputed data, int k, long idx) {
        long intervalLen = data.fib.get(k - 1);
        if (idx >= intervalLen - 1) {
            return data.intervalSum[k];
        }
        if (k <= 2)
            return BigInteger.ZERO;

        long p = data.prefixLen[k];
        if (idx < p) {
            return tri(idx);
        }

        long tailIdx = idx - p;
        return tri(p - 1).add(prefixTail(data, k, tailIdx));
    }

    static BigInteger fastSumM(long n, Precomputed data) {
        if (n == 0)
            return BigInteger.ZERO;

        int k = 1;
        while (k + 1 < data.fib.size() && data.fib.get(k + 1) <= n) {
            k++;
        }

        BigInteger fullBefore = data.intervalPrefixSum[k - 1];
        long idx = n - data.fib.get(k);
        return fullBefore.add(prefixInterval(data, k, idx));
    }

    static String solve() {
        Precomputed data = new Precomputed(kLimit);
        BigInteger total = fastSumM(kLimit, data);
        long ans = total.remainder(BigInteger.valueOf(kMod)).longValue();
        return Long.toString(ans);
    }

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