public class Euler149 {
    public static void main(String[] args) {
        int size = 2000, total = size * size;
        long[] s = new long[total + 1];
        for (int k = 1; k <= 55; k++)
            s[k] = ((100003L - 200003L * k + 300007L * k * k * k) % 1000000 + 1000000) % 1000000 - 500000;
        for (int k = 56; k <= total; k++)
            s[k] = (s[k - 24] + s[k - 55] + 1000000) % 1000000 - 500000;
        long best = Long.MIN_VALUE;
        // Rows
        for (int r = 0; r < size; r++) {
            long cur = Long.MIN_VALUE / 4;
            for (int c = 0; c < size; c++) {
                long v = s[r * size + c + 1];
                cur = Math.max(v, cur + v);
                best = Math.max(best, cur);
            }
        }
        // Cols
        for (int c = 0; c < size; c++) {
            long cur = Long.MIN_VALUE / 4;
            for (int r = 0; r < size; r++) {
                long v = s[r * size + c + 1];
                cur = Math.max(v, cur + v);
                best = Math.max(best, cur);
            }
        }
        // Diag \
        for (int cs = 0; cs < size; cs++) {
            long cur = Long.MIN_VALUE / 4;
            for (int r = 0, c = cs; r < size && c < size; r++, c++) {
                long v = s[r * size + c + 1];
                cur = Math.max(v, cur + v);
                best = Math.max(best, cur);
            }
        }
        for (int rs = 1; rs < size; rs++) {
            long cur = Long.MIN_VALUE / 4;
            for (int r = rs, c = 0; r < size && c < size; r++, c++) {
                long v = s[r * size + c + 1];
                cur = Math.max(v, cur + v);
                best = Math.max(best, cur);
            }
        }
        // Diag /
        for (int cs = 0; cs < size; cs++) {
            long cur = Long.MIN_VALUE / 4;
            for (int r = 0, c = cs; r < size && c >= 0; r++, c--) {
                long v = s[r * size + c + 1];
                cur = Math.max(v, cur + v);
                best = Math.max(best, cur);
            }
        }
        for (int rs = 1; rs < size; rs++) {
            long cur = Long.MIN_VALUE / 4;
            for (int r = rs, c = size - 1; r < size && c >= 0; r++, c--) {
                long v = s[r * size + c + 1];
                cur = Math.max(v, cur + v);
                best = Math.max(best, cur);
            }
        }
        System.out.println(best);
    }
}