public class Euler764 {

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

    static long pow4(long x) {
        return x * x * x * x;
    }

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

    static long solveMod(long n, long mod) {
        long total = 0;

        long qMax = iroot4(2 * n);
        for (long q = 1; q <= qMax; q += 2) {
            long q4 = pow4(q);
            if (q4 > 2 * n)
                continue;
            long lim = 2 * n - q4;
            long pMax = iroot4(lim);
            if (pMax >= q)
                pMax = q - 1;
            if ((pMax & 1) == 0)
                pMax--;

            for (long p = 1; p <= pMax; p += 2) {
                if (gcd(p, q) != 1)
                    continue;
                long p4 = pow4(p);
                long z = (p4 + q4) / 2;
                if (z > n)
                    continue;
                long x = (q4 - p4) / 8;
                long y = p * q;
                if (y > n)
                    continue;

                long term = (x + y + z) % mod;
                total = (total + term) % mod;
            }
        }

        long sMax = iroot4(n / 4);
        for (long s = 1; s <= sMax; s += 2) {
            long s4 = pow4(s);
            if (s4 > n / 4)
                break;
            long rem = n / 4 - s4;
            long rMax = iroot4(rem / 4);

            for (long r = 1; r <= rMax; r++) {
                if (gcd(r, s) != 1)
                    continue;
                long r4 = pow4(r);
                long z = 4 * (s4 + 4 * r4);
                if (z > n)
                    continue;

                long a = 4 * r4;
                long x = (s4 >= a) ? (s4 - a) : (a - s4);
                long y = 4 * r * s;
                if (y > n)
                    continue;

                long term = (x + y + z) % mod;
                total = (total + term) % mod;
            }
        }

        return total;
    }

    public static String solve() {
        long ans = solveMod(10000000000000000L, 1000000000L);
        return Long.toString(ans);
    }

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