import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
import java.util.concurrent.Callable;

public class Euler721 {
    static final long kMod = 999999937L;

    static long isqrt(long n) {
        long r = (long) Math.sqrt(n);
        while ((r + 1) * (r + 1) <= n)
            r++;
        while (r > 0 && r * r > n)
            r--;
        return r;
    }

    static class Worker implements Callable<Long> {
        long l, r;

        Worker(long l, long r) {
            this.l = l;
            this.r = r;
        }

        @Override
        public Long call() {
            long partialSum = 0;
            long m = isqrt(l);
            if (m * m < l)
                m++;
            long sq = m * m;

            for (long a = l; a <= r; ++a) {
                while (sq < a) {
                    m++;
                    sq = m * m;
                }
                boolean isSquare = (sq == a);
                long n = a * a;
                long aMod = a % kMod;

                long baseX = m % kMod;
                long baseY = 1;
                long resX = 1;
                long resY = 0;

                while (n > 0) {
                    if ((n & 1) != 0) {
                        long nx = (resX * baseX % kMod + resY * baseY % kMod * aMod % kMod) % kMod;
                        long ny = (resX * baseY % kMod + resY * baseX % kMod) % kMod;
                        resX = nx;
                        resY = ny;
                    }
                    n >>= 1;
                    if (n > 0) {
                        long nx = (baseX * baseX % kMod + baseY * baseY % kMod * aMod % kMod) % kMod;
                        long ny = (2 * baseX * baseY) % kMod;
                        baseX = nx;
                        baseY = ny;
                    }
                }

                long val = (2 * resX) % kMod;
                if (!isSquare) {
                    val = (val + kMod - 1) % kMod;
                }

                partialSum = (partialSum + val) % kMod;
            }
            return partialSum;
        }
    }

    public static String solve() {
        long limit = 5000000;
        int threads = Runtime.getRuntime().availableProcessors();
        if (threads < 1)
            threads = 1;

        long chunk = limit / threads;
        long rem = limit % threads;

        ExecutorService executor = Executors.newFixedThreadPool(threads);
        List<Future<Long>> futures = new ArrayList<>();

        long curr = 1;
        for (int t = 0; t < threads; ++t) {
            long length = chunk + (t < rem ? 1 : 0);
            if (length > 0) {
                futures.add(executor.submit(new Worker(curr, curr + length - 1)));
            }
            curr += length;
        }

        long total = 0;
        try {
            for (Future<Long> f : futures) {
                total = (total + f.get()) % kMod;
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
        executor.shutdown();

        return Long.toString(total);
    }

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