import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.IntStream;

public class Euler439 {
    static final long MOD = 1000000000L;
    static final long N = 100000000000L;
    static final int SIEVE_LIMIT = 5000000;

    static long sumArithMod(long l, long r) {
        long count = r - l + 1;
        long sum = l + r;
        long val;
        if (count % 2 == 0) {
            val = ((count / 2) % MOD) * (sum % MOD) % MOD;
        } else {
            val = (count % MOD) * ((sum / 2) % MOD) % MOD;
        }
        return val;
    }

    static long sumSigmaPrefix(long M) {
        long total = 0;
        long l = 1;
        while (l <= M) {
            long q = M / l;
            long r = M / q;
            long q_sum;
            if (q % 2 == 0) {
                q_sum = ((q / 2) % MOD) * ((q + 1) % MOD) % MOD;
            } else {
                q_sum = (q % MOD) * (((q + 1) / 2) % MOD) % MOD;
            }

            long len = (r - l + 1) % MOD;
            total = (total + q_sum * len % MOD) % MOD;
            l = r + 1;
        }
        return total;
    }

    static class MobiusPrefix {
        int limit;
        byte[] mu;
        int[] prefix;
        Map<Long, Long> cache = new HashMap<>();

        MobiusPrefix(int limit) {
            this.limit = limit;
            mu = new byte[limit + 1];
            prefix = new int[limit + 1];
            build();
        }

        void build() {
            byte[] isComp = new byte[limit + 1];
            List<Integer> primes = new ArrayList<>();
            mu[1] = 1;
            for (int i = 2; i <= limit; i++) {
                if (isComp[i] == 0) {
                    primes.add(i);
                    mu[i] = -1;
                }
                for (int p : primes) {
                    long v = (long) i * p;
                    if (v > limit)
                        break;
                    isComp[(int) v] = 1;
                    if (i % p == 0) {
                        mu[(int) v] = 0;
                        break;
                    }
                    mu[(int) v] = (byte) -mu[i];
                }
            }
            long running = 0;
            for (int i = 1; i <= limit; i++) {
                long term = ((long) i * mu[i]) % MOD;
                if (term < 0)
                    term += MOD;
                running = (running + term) % MOD;
                prefix[i] = (int) running;
            }
        }

        long sumPrefix(long n) {
            if (n <= 0)
                return 0;
            if (n <= limit)
                return prefix[(int) n];
            if (cache.containsKey(n))
                return cache.get(n);

            long ans = 1;
            long l = 2;
            while (l <= n) {
                long v = n / l;
                long r = n / v;
                long sumLr = sumArithMod(l, r);
                long sub = (sumLr * sumPrefix(v)) % MOD;
                ans = (ans - sub + MOD) % MOD;
                l = r + 1;
            }

            cache.put(n, ans);
            return ans;
        }
    }

    static class RangeData {
        long l, r, m, muSum;

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

    public static String solve() {
        MobiusPrefix pref = new MobiusPrefix(SIEVE_LIMIT);

        List<RangeData> ranges = new ArrayList<>();
        long l = 1;
        while (l <= N) {
            long q = N / l;
            long r = N / q;
            ranges.add(new RangeData(l, r, q));
            l = r + 1;
        }

        long prevPrefix = 0;
        List<RangeData> validRanges = new ArrayList<>();
        for (RangeData rng : ranges) {
            long prefR = pref.sumPrefix(rng.r);
            long prefLm1 = (rng.l == 1) ? 0 : prevPrefix;
            long muSum = (prefR - prefLm1 + MOD) % MOD;
            prevPrefix = prefR;

            if (muSum != 0) {
                rng.muSum = muSum;
                validRanges.add(rng);
            }
        }

        int numThreads = Math.min(Runtime.getRuntime().availableProcessors(), validRanges.size());
        if (numThreads < 1)
            numThreads = 1;

        final int threads = numThreads;
        long total = IntStream.range(0, threads).parallel().mapToLong(i -> {
            int begin = i * validRanges.size() / threads;
            int end = (i + 1) * validRanges.size() / threads;
            long localSum = 0;
            for (int k = begin; k < end; k++) {
                RangeData rng = validRanges.get(k);
                long a = sumSigmaPrefix(rng.m);
                long term = rng.muSum * a % MOD * a % MOD;
                localSum = (localSum + term) % MOD;
            }
            return localSum;
        }).sum();

        return Long.toString(total % MOD);
    }

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