import java.math.BigInteger;

public class Euler748 {
    static final long kMod = 1000000000L;

    static long gcd(long a, long b) {
        while (b != 0) {
            long t = b;
            b = a % b;
            a = t;
        }
        return a;
    }

    static long isqrtU64(long n) {
        if (n == 0)
            return 0;
        long x = (long) Math.sqrt(n);
        while ((x + 1) * (x + 1) <= n)
            x++;
        while (x * x > n)
            x--;
        return x;
    }

    static long maxR(long nLimit) {
        BigInteger bigN = BigInteger.valueOf(nLimit);
        BigInteger rhs = BigInteger.valueOf(2).multiply(bigN).multiply(bigN);
        long lo = 0;
        long hi = (long) Math.sqrt(nLimit) + 10;

        BigInteger thirteen = BigInteger.valueOf(13);

        while (true) {
            BigInteger bigHi = BigInteger.valueOf(hi);
            BigInteger lhs = thirteen.multiply(bigHi).multiply(bigHi).multiply(bigHi).multiply(bigHi);
            if (lhs.compareTo(rhs) <= 0) {
                hi *= 2;
            } else {
                break;
            }
        }

        while (lo + 1 < hi) {
            long mid = lo + (hi - lo) / 2;
            BigInteger bigMid = BigInteger.valueOf(mid);
            BigInteger lhs = thirteen.multiply(bigMid).multiply(bigMid).multiply(bigMid).multiply(bigMid);

            if (lhs.compareTo(rhs) <= 0) {
                lo = mid;
            } else {
                hi = mid;
            }
        }

        return lo;
    }

    static BigInteger S(long nLimit) {
        long rLimit = maxR(nLimit);
        long mLimit = isqrtU64(rLimit);

        BigInteger total = BigInteger.ZERO;
        BigInteger bigNLimit = BigInteger.valueOf(nLimit);

        for (long m = 1; m <= mLimit; ++m) {
            for (long n = 0; n < m; ++n) {
                if (((m - n) & 1) == 0)
                    continue;
                if (gcd(m, n) != 1)
                    continue;

                long r = m * m + n * n;
                if (r > rLimit)
                    continue;

                long u = m * m - n * n;
                long v = 2 * m * n;

                long[][] cand = {
                        { Math.abs(3 * u - 2 * v), Math.abs(2 * u + 3 * v) },
                        { Math.abs(3 * u + 2 * v), Math.abs(2 * u - 3 * v) }
                };

                for (int i = 0; i < 2; ++i) {
                    if (i == 1 && cand[1][0] == cand[0][0] && cand[1][1] == cand[0][1]) {
                        continue;
                    }

                    long p = cand[i][0];
                    long q = cand[i][1];
                    if (p == 0 || q == 0)
                        continue;
                    if (p < q) {
                        long temp = p;
                        p = q;
                        q = temp;
                    }

                    if (gcd(p, q) != 1)
                        continue;

                    BigInteger x = BigInteger.valueOf(q).multiply(BigInteger.valueOf(r));
                    BigInteger y = BigInteger.valueOf(p).multiply(BigInteger.valueOf(r));
                    BigInteger z = BigInteger.valueOf(p).multiply(BigInteger.valueOf(q));

                    if (x.compareTo(bigNLimit) > 0 || y.compareTo(bigNLimit) > 0 || z.compareTo(bigNLimit) > 0) {
                        continue;
                    }

                    total = total.add(x).add(y).add(z);
                }
            }
        }

        return total;
    }

    public static String solve() {
        BigInteger ans = S(10000000000000000L).remainder(BigInteger.valueOf(kMod));
        return String.format("%09d", ans.longValue());
    }

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