public class Euler663 {

    static class Node {
        long sum = 0;
        long pref = 0;
        long suff = 0;
        long best = 0;
    }

    static class MaxSubarrayTracker {
        int n;
        int bsz;
        int blockCount;
        int size;
        long[] arr;
        Node[] seg;

        MaxSubarrayTracker(int n, int blockSize) {
            this.n = n;
            this.bsz = blockSize;
            this.blockCount = (n + bsz - 1) / bsz;
            this.arr = new long[n];
            this.size = 1;
            while (this.size < this.blockCount)
                this.size <<= 1;
            this.seg = new Node[2 * this.size];
            for (int i = 0; i < 2 * this.size; ++i) {
                this.seg[i] = new Node();
            }
        }

        void add(int idx, long delta) {
            arr[idx] += delta;
            int b = idx / bsz;
            recomputeBlock(b, seg[size + b]);

            int pos = size + b;
            pos >>= 1;
            while (pos > 0) {
                mergeNodes(seg[pos << 1], seg[(pos << 1) | 1], seg[pos]);
                pos >>= 1;
            }
        }

        long maxSubarray() {
            return seg[1].best;
        }

        void recomputeBlock(int b, Node x) {
            int l = b * bsz;
            int r = Math.min(n, l + bsz);

            x.sum = 0;
            x.pref = 0;
            x.suff = 0;
            x.best = 0;
            long cur = 0;
            long runPref = 0;

            for (int i = l; i < r; ++i) {
                long v = arr[i];
                x.sum += v;
                runPref += v;
                if (runPref > x.pref)
                    x.pref = runPref;

                cur = Math.max(0L, cur + v);
                if (cur > x.best)
                    x.best = cur;
            }

            long runSuff = 0;
            for (int i = r - 1; i >= l; --i) {
                runSuff += arr[i];
                if (runSuff > x.suff)
                    x.suff = runSuff;
            }
        }

        void mergeNodes(Node a, Node b, Node c) {
            c.sum = a.sum + b.sum;
            c.pref = Math.max(a.pref, a.sum + b.pref);
            c.suff = Math.max(b.suff, b.sum + a.suff);
            long m1 = Math.max(a.best, b.best);
            long m2 = a.suff + b.pref;
            c.best = Math.max(m1, m2);
        }
    }

    static String solveRange(int n, int lFromExclusive, int lToInclusive) {
        int blockSize = 128; // Optimized for performance and size
        MaxSubarrayTracker tracker = new MaxSubarrayTracker(n, blockSize);

        int need = 2 * lToInclusive;
        int[] t = new int[need];
        t[0] = 0;
        t[1] = 0;
        t[2] = 1 % n;
        for (int k = 3; k < need; ++k) {
            long v = (long) t[k - 1] + t[k - 2] + t[k - 3];
            t[k] = (int) (v % n);
        }

        java.math.BigInteger answer = java.math.BigInteger.ZERO;
        for (int i = 1; i <= lToInclusive; ++i) {
            int idx = t[2 * i - 2];
            long delta = 2L * t[2 * i - 1] - n + 1L;
            tracker.add(idx, delta);
            if (i > lFromExclusive) {
                answer = answer.add(java.math.BigInteger.valueOf(tracker.maxSubarray()));
            }
        }
        return answer.toString();
    }

    public static String solve() {
        return solveRange(10000003, 10000000, 10200000);
    }

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