import java.util.*;

public class Euler340 {

    static final long MOD = 1000000000L;

    static long modMul(long x, long y) {
        // Can overflow 64-bit if x,y ~ 10^9, so use 128-bit via BigInteger or split.
        // Or since x, y < 10^9, x*y < 10^18, which fits in long perfectly!
        return (x * y) % MOD;
    }

    static long sClosedMod1e9(long a, long b, long c) {
        long d = a - c;
        long q = b / a;
        long r = b % a;

        long sumN = 0;
        if ((b & 1) == 0) {
            sumN = modMul((b / 2) % MOD, (b + 1) % MOD);
        } else {
            sumN = modMul(b % MOD, ((b + 1) / 2) % MOD);
        }

        long termLinear = modMul((b + 1) % MOD, (4 * (d % MOD)) % MOD);

        java.math.BigInteger aBig = java.math.BigInteger.valueOf(a);
        java.math.BigInteger qBig = java.math.BigInteger.valueOf(q);
        java.math.BigInteger sumFloor = aBig.multiply(qBig).multiply(qBig.subtract(java.math.BigInteger.ONE))
                .divide(java.math.BigInteger.valueOf(2))
                .add(java.math.BigInteger.valueOf(r + 1).multiply(qBig));

        long sumFloorMod = sumFloor.remainder(java.math.BigInteger.valueOf(MOD)).longValue();
        long termFloor = modMul((a + 3 * d) % MOD, sumFloorMod);

        return (sumN + termLinear + termFloor) % MOD;
    }

    public static String solve() {
        long a = 1801088541L;
        long b = 558545864083284007L;
        long c = 35831808L;
        long ans = sClosedMod1e9(a, b, c);
        return String.valueOf(ans);
    }

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