import java.math.BigInteger;

public class Euler880 {

    static final long MOD = 1031L * 1031L * 1031L + 2L;

    static long isqrtU64(long n) {
        long x = (long) Math.sqrt(n);
        while (new java.math.BigInteger(String.valueOf(x + 1)).pow(2)
                .compareTo(new java.math.BigInteger(String.valueOf(n))) <= 0)
            ++x;
        while (new java.math.BigInteger(String.valueOf(x)).pow(2)
                .compareTo(new java.math.BigInteger(String.valueOf(n))) > 0)
            --x;
        return x;
    }

    static long icbrtU64(long n) {
        long x = (long) Math.cbrt(n);
        while (new java.math.BigInteger(String.valueOf(x + 1)).pow(3)
                .compareTo(new java.math.BigInteger(String.valueOf(n))) <= 0)
            ++x;
        while (new java.math.BigInteger(String.valueOf(x)).pow(3)
                .compareTo(new java.math.BigInteger(String.valueOf(n))) > 0)
            --x;
        return x;
    }

    static long i4rtU64(long n) {
        long x = (long) Math.pow(n, 0.25);
        while (new java.math.BigInteger(String.valueOf(x + 1)).pow(4)
                .compareTo(new java.math.BigInteger(String.valueOf(n))) <= 0)
            ++x;
        while (new java.math.BigInteger(String.valueOf(x)).pow(4)
                .compareTo(new java.math.BigInteger(String.valueOf(n))) > 0)
            --x;
        return x;
    }

    static int[] precomputeCubeFree(int limit) {
        int[] spf = new int[limit + 1];
        for (int i = 0; i <= limit; ++i)
            spf[i] = i;
        for (int i = 2; (long) i * i <= limit; ++i) {
            if (spf[i] == i) {
                for (long j = (long) i * i; j <= limit; j += i) {
                    if (spf[(int) j] == (int) j)
                        spf[(int) j] = i;
                }
            }
        }

        int[] cf = new int[limit + 1];
        if (limit >= 1)
            cf[1] = 1;
        for (int n = 2; n <= limit; ++n) {
            int x = n;
            long res = 1;
            while (x > 1) {
                int p = spf[x];
                int e = 0;
                while (x % p == 0) {
                    x /= p;
                    ++e;
                }
                int r = e % 3;
                if (r == 1)
                    res *= p;
                else if (r == 2)
                    res *= (long) p * p;
            }
            cf[n] = (int) res;
        }
        return cf;
    }

    static long sumsqMod(long n) {
        BigInteger bn = BigInteger.valueOf(n);
        BigInteger s = bn.multiply(bn.add(BigInteger.ONE))
                .multiply(bn.multiply(BigInteger.valueOf(2)).add(BigInteger.ONE));
        s = s.divide(BigInteger.valueOf(6));
        return s.mod(BigInteger.valueOf(MOD)).longValue();
    }

    static long gcd(long a, long b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }

    // I will use BigInteger to translate __int128 ops since intermediate values top
    // 128 bit.

    static long solveHMod(long N) {
        long qMax = i4rtU64(4L * N);

        long maxPEven2 = 0;
        if (N >= 4) {
            long c = icbrtU64(N / 4);
            if (c > 1)
                maxPEven2 = (c - 1) / 2;
        }
        long maxPOdd1 = 0;
        long c_odd = icbrtU64(N);
        if (c_odd > 1)
            maxPOdd1 = (c_odd - 1) / 4;

        long maxP = Math.max(maxPEven2, maxPOdd1);

        int limit = (int) (Math.max(4L * maxP, 2L * qMax) + 16);
        int[] cubeFree = precomputeCubeFree(limit);

        long ans = 0;
        BigInteger bN = BigInteger.valueOf(N);

        for (long q = 1; q <= qMax; ++q) {
            if (q % 2 != 0) {
                long ndiv = N / q;
                long c = icbrtU64(ndiv);
                if (c <= q)
                    continue;
                long pMax = (c - q) / 4;
                if (pMax == 0)
                    continue;

                int dx = cubeFree[(int) q];

                for (long p = 1; p <= pMax; ++p) {
                    if (gcd(p, q) != 1)
                        continue;
                    if (p == 2L * q)
                        continue;

                    long t = q + 4L * p;
                    BigInteger bt = BigInteger.valueOf(t);
                    BigInteger bt3 = bt.pow(3);
                    BigInteger x0 = BigInteger.valueOf(q).multiply(bt3);

                    long u = p - 2L * q;
                    BigInteger bu = BigInteger.valueOf(u);
                    BigInteger bu3 = bu.pow(3);
                    BigInteger y0 = BigInteger.valueOf(4L * p).multiply(bu3);

                    BigInteger absY = y0.abs();
                    BigInteger max0 = x0.compareTo(absY) > 0 ? x0 : absY;
                    if (max0.compareTo(bN) > 0)
                        continue;

                    int dy = cubeFree[(int) (4 * p)];
                    if (dx == dy)
                        continue;

                    long mmax = isqrtU64(bN.divide(max0).longValue());
                    long s2 = sumsqMod(mmax);

                    long absSum = x0.add(absY).mod(BigInteger.valueOf(MOD)).longValue();
                    ans = (ans + (absSum * s2) % MOD) % MOD;
                }
            } else {
                long ndiv = N / (2L * q);
                long c = icbrtU64(ndiv);
                long halfq = q / 2L;
                if (c <= halfq)
                    continue;
                long pMax = (c - halfq) / 2;
                if (pMax == 0)
                    continue;

                int dx = cubeFree[(int) (2 * q)];

                for (long p = 1; p <= pMax; ++p) {
                    if (gcd(p, q) != 1)
                        continue;
                    if (p == 2L * q)
                        continue;

                    long t = halfq + 2L * p;
                    BigInteger bt = BigInteger.valueOf(t);
                    BigInteger bt3 = bt.pow(3);
                    BigInteger x0 = BigInteger.valueOf(2L * q).multiply(bt3);

                    long u = p - 2L * q;
                    BigInteger bu = BigInteger.valueOf(u);
                    BigInteger bu3 = bu.pow(3);
                    BigInteger y0 = BigInteger.valueOf(p).multiply(bu3);

                    BigInteger absY = y0.abs();
                    BigInteger max0 = x0.compareTo(absY) > 0 ? x0 : absY;
                    if (max0.compareTo(bN) > 0)
                        continue;

                    int dy = cubeFree[(int) p];
                    if (dx == dy)
                        continue;

                    long mmax = isqrtU64(bN.divide(max0).longValue());
                    long s2 = sumsqMod(mmax);

                    long absSum = x0.add(absY).mod(BigInteger.valueOf(MOD)).longValue();
                    ans = (ans + (absSum * s2) % MOD) % MOD;
                }
            }
        }
        return ans;
    }

    public static String solve() {
        return Long.toString(solveHMod(1000000000000000L));
    }

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