import java.math.BigInteger;
import java.util.concurrent.atomic.AtomicLong;

public class Euler791 {

    static final long MOD = 433494437L;

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

    static long ceilSqrtLl(long x) {
        if (x <= 0)
            return 0;
        long r = isqrtLl(x);
        if (r * r < x)
            r++;
        return r;
    }

    static long sumInterval(long L, long H, long N0) {
        if ((L & 1) == 0)
            L++;
        if ((H & 1) == 0)
            H--;
        if (L > H)
            return 0;

        long cnt = (H - L) / 2 + 1;
        BigInteger biCnt = BigInteger.valueOf(cnt);
        BigInteger biT = BigInteger.valueOf(cnt - 1);
        BigInteger biL = BigInteger.valueOf(L);
        BigInteger biN0 = BigInteger.valueOf(N0);

        BigInteger sumI = biCnt.multiply(biT).divide(BigInteger.TWO);
        BigInteger sumI2 = biT.multiply(biCnt).multiply(biT.multiply(BigInteger.TWO).add(BigInteger.ONE))
                .divide(BigInteger.valueOf(6));

        BigInteger sumC = biCnt.multiply(biL).add(sumI.multiply(BigInteger.TWO));
        BigInteger sumC2 = biCnt.multiply(biL).multiply(biL)
                .add(BigInteger.valueOf(4).multiply(biL).multiply(sumI))
                .add(BigInteger.valueOf(4).multiply(sumI2));

        BigInteger sumNum = biCnt.multiply(biN0).add(sumC2).add(sumC.multiply(BigInteger.TWO));
        BigInteger sumS = sumNum.divide(BigInteger.TWO);

        long mod = sumS.remainder(BigInteger.valueOf(MOD)).longValue();
        if (mod < 0)
            mod += MOD;
        return mod;
    }

    static long sValue(long n) {
        if (n <= 0)
            return 0;
        long R = 8 * n;

        long aMax = isqrtLl(R + 3) - 2;
        if (aMax < 1)
            return 0;
        if ((aMax & 1) == 0)
            aMax--;

        int numThreads = Runtime.getRuntime().availableProcessors();
        if (numThreads <= 0)
            numThreads = 1;

        AtomicLong nextA = new AtomicLong(1);
        long[] partials = new long[numThreads];
        Thread[] threads = new Thread[numThreads];

        final long aMaxFinal = aMax;

        for (int t = 0; t < numThreads; t++) {
            final int tid = t;
            threads[t] = new Thread(() -> {
                long local = 0;
                while (true) {
                    long A = nextA.getAndAdd(2);
                    if (A > aMaxFinal)
                        break;

                    long A2 = A * A;
                    long D = R - A2 - 4 * A - 1;
                    if (D < 0)
                        continue;

                    long B_max = isqrtLl(D) - 2;
                    if (B_max < -1)
                        continue;
                    if (B_max > A)
                        B_max = A;

                    for (long B = -1; B <= B_max; B += 2) {
                        long B2 = B * B;
                        long L = R - A2 - B2 - 4 * A - 4 * B - 5;
                        if (L < 0)
                            continue;
                        long C_max = isqrtLl(L);

                        long C_low = Math.max(-C_max, -B - 2);
                        long C_high = Math.min(C_max, B);
                        if (C_low > C_high)
                            continue;

                        long Lmin = 11 - A2 - B2;
                        long N0 = A2 + B2 + 2 * A + 2 * B + 3;

                        if (Lmin <= 0) {
                            local += sumInterval(C_low, C_high, N0);
                            if (local >= MOD)
                                local -= MOD;
                        } else {
                            long cmin = ceilSqrtLl(Lmin);
                            if ((cmin & 1) == 0)
                                cmin++;

                            long neg_high = Math.min(C_high, -cmin);
                            if (C_low <= neg_high) {
                                local += sumInterval(C_low, neg_high, N0);
                                if (local >= MOD)
                                    local -= MOD;
                            }

                            long pos_low = Math.max(C_low, cmin);
                            if (pos_low <= C_high) {
                                local += sumInterval(pos_low, C_high, N0);
                                if (local >= MOD)
                                    local -= MOD;
                            }
                        }
                    }
                }
                partials[tid] = local;
            });
            threads[t].start();
        }

        long ans = 0;
        for (int t = 0; t < numThreads; t++) {
            try {
                threads[t].join();
                ans += partials[t];
                if (ans >= MOD)
                    ans -= MOD;
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
        return ans;
    }

    public static String solve() {
        return Long.toString(sValue(100000000L));
    }

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