import java.util.*;
import java.math.BigInteger;

public class Euler334 {

    static List<Long> generateBeans(int count) {
        List<Long> beans = new ArrayList<>(count);
        long t = 123456;
        for (int i = 0; i < count; i++) {
            if ((t & 1) == 0) {
                t /= 2;
            } else {
                t = (t / 2) ^ 926252L;
            }
            long b = (t & ((1L << 11) - 1)) + 1;
            beans.add(b);
        }
        return beans;
    }

    static BigInteger sumSquaresArith(BigInteger first, BigInteger n) {
        if (n.compareTo(BigInteger.ZERO) <= 0)
            return BigInteger.ZERO;
        BigInteger two = BigInteger.valueOf(2);
        BigInteger six = BigInteger.valueOf(6);

        BigInteger nMinus1 = n.subtract(BigInteger.ONE);
        BigInteger sumK = n.multiply(nMinus1).divide(two);

        BigInteger twoNMinus1 = n.multiply(two).subtract(BigInteger.ONE);
        BigInteger sumK2 = n.multiply(nMinus1).multiply(twoNMinus1).divide(six);

        BigInteger term1 = n.multiply(first).multiply(first);
        BigInteger term2 = two.multiply(first).multiply(sumK);

        return term1.add(term2).add(sumK2);
    }

    static BigInteger floorDiv(BigInteger a, BigInteger b) {
        return a.divide(b); // In Java, BigInteger.divide truncates toward zero. But since both are positive
                            // here, it is actually floor division.
        // Wait, for negative 'a', it truncates toward zero instead of floor.
        // Let's implement proper floor div:
    }

    static BigInteger properFloorDiv(BigInteger a, BigInteger b) {
        BigInteger[] qr = a.divideAndRemainder(b);
        BigInteger q = qr[0];
        BigInteger r = qr[1];
        if (r.compareTo(BigInteger.ZERO) < 0) {
            if (b.compareTo(BigInteger.ZERO) > 0)
                q = q.subtract(BigInteger.ONE);
            else
                q = q.add(BigInteger.ONE);
        }
        return q;
    }

    static BigInteger properFloorMod(BigInteger a, BigInteger b) {
        BigInteger[] qr = a.divideAndRemainder(b);
        BigInteger r = qr[1];
        if (r.compareTo(BigInteger.ZERO) < 0) {
            if (b.compareTo(BigInteger.ZERO) > 0)
                r = r.add(b);
            else
                r = r.subtract(b);
        }
        return r;
    }

    public static String solve() {
        List<Long> beans = generateBeans(1500);

        BigInteger total = BigInteger.ZERO;
        BigInteger firstMoment = BigInteger.ZERO;
        BigInteger secondMoment = BigInteger.ZERO;

        for (int i = 0; i < beans.size(); i++) {
            BigInteger b = BigInteger.valueOf(beans.get(i));
            BigInteger ib = BigInteger.valueOf(i);

            total = total.add(b);
            firstMoment = firstMoment.add(ib.multiply(b));
            secondMoment = secondMoment.add(ib.multiply(ib).multiply(b));
        }

        BigInteger B = total;
        BigInteger bMinus1 = B.subtract(BigInteger.ONE);
        BigInteger bPair = B.multiply(bMinus1).divide(BigInteger.valueOf(2));

        BigInteger targetShift = firstMoment.subtract(bPair);

        BigInteger q = properFloorDiv(targetShift, B);
        BigInteger r = properFloorMod(targetShift, B);

        BigInteger n1 = B.subtract(r);
        BigInteger n2 = r;

        BigInteger qFinal = sumSquaresArith(q, n1).add(sumSquaresArith(q.add(n1).add(BigInteger.ONE), n2));

        BigInteger diff = qFinal.subtract(secondMoment);
        return diff.divide(BigInteger.valueOf(2)).toString();
    }

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