import java.math.BigInteger;

public class Euler507 {
    static final long MOD = 10000000L;

    static long floorDiv(long a, long b) {
        long q = a / b, r = a % b;
        if (r != 0 && ((r > 0) != (b > 0)))
            q--;
        return q;
    }

    static long abs64(long v) {
        return v < 0 ? -v : v;
    }

    static BigInteger l1(long[] v) {
        return BigInteger.valueOf(abs64(v[0])).add(BigInteger.valueOf(abs64(v[1])))
                .add(BigInteger.valueOf(abs64(v[2])));
    }

    static BigInteger l1diff(long[] w, long[] v, long t) {
        BigInteger s = BigInteger.ZERO;
        for (int i = 0; i < 3; i++) {
            long val = w[i] - t * v[i];
            s = s.add(BigInteger.valueOf(abs64(val)));
        }
        return s;
    }

    static long bestT(long[] v, long[] w) {
        long[] cand = new long[8];
        int c = 0;
        cand[c++] = 0;
        for (int i = 0; i < 3; i++)
            if (v[i] != 0) {
                long q = floorDiv(w[i], v[i]);
                cand[c++] = q;
                cand[c++] = q + 1;
            }
        long best = cand[0];
        BigInteger bv = l1diff(w, v, best);
        for (int i = 1; i < c; i++) {
            BigInteger val = l1diff(w, v, cand[i]);
            if (val.compareTo(bv) < 0) {
                bv = val;
                best = cand[i];
            }
        }
        return best;
    }

    static BigInteger shortestL1(long[] a, long[] b) {
        while (true) {
            if (l1(b).compareTo(l1(a)) < 0) {
                long[] tmp = a;
                a = b;
                b = tmp;
            }
            long t = bestT(a, b);
            long[] nb = { b[0] - t * a[0], b[1] - t * a[1], b[2] - t * a[2] };
            if (l1(nb).compareTo(l1(b)) < 0)
                b = nb;
            else
                break;
        }
        BigInteger la = l1(a), lb = l1(b);
        if (la.signum() == 0)
            return lb;
        if (lb.signum() == 0)
            return la;
        return la.min(lb);
    }

    static long[][] matMul(long[][] a, long[][] b) {
        long[][] r = new long[3][3];
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++) {
                long s = 0;
                for (int k = 0; k < 3; k++)
                    s = (s + a[i][k] * b[k][j]) % MOD;
                r[i][j] = s;
            }
        return r;
    }

    static long[][] matPow(long[][] base, long exp) {
        long[][] res = { { 1, 0, 0 }, { 0, 1, 0 }, { 0, 0, 1 } };
        while (exp > 0) {
            if ((exp & 1) == 1)
                res = matMul(res, base);
            base = matMul(base, base);
            exp >>= 1;
        }
        return res;
    }

    static long[] tribState(long n) {
        if (n == 1)
            return new long[] { 0, 0, 1 };
        if (n == 2)
            return new long[] { 1, 0, 0 };
        long[][] base = { { 1, 1, 1 }, { 1, 0, 0 }, { 0, 1, 0 } };
        long[][] p = matPow(base, n - 2);
        return new long[] { p[0][0], p[1][0], p[2][0] };
    }

    static BigInteger sumRange(long nStart, long nEnd) {
        long idxStart = 12 * nStart - 11, idxEnd = 12 * nEnd;
        long[] st = tribState(idxStart);
        long a = st[2], b = st[1], c = st[0];
        long total = idxEnd - idxStart + 1;
        long[] rvals = new long[12];
        int pos = 0;
        BigInteger sum = BigInteger.ZERO;
        for (long i = 0; i < total; i++) {
            rvals[pos++] = c;
            if (pos == 12) {
                long[] v = { rvals[0] - rvals[1], rvals[2] + rvals[3], rvals[4] * rvals[5] };
                long[] w = { rvals[6] - rvals[7], rvals[8] + rvals[9], rvals[10] * rvals[11] };
                sum = sum.add(shortestL1(v, w));
                pos = 0;
            }
            long next = a + b + c;
            if (next >= MOD) {
                next -= MOD;
                if (next >= MOD)
                    next -= MOD;
            }
            a = b;
            b = c;
            c = next;
        }
        return sum;
    }

    public static void main(String[] args) {
        System.out.println(sumRange(1, 20000000));
    }
}