import java.util.*;

public class Euler319 {
    static final long MOD = 1000000000L;
    static final long MOD2 = 2 * MOD;

    static long modNorm(long x) {
        x %= MOD;
        if (x < 0)
            x += MOD;
        return x;
    }

    static long powMod(long base, long exp, long mod) {
        long res = 1 % mod;
        base %= mod;
        while (exp > 0) {
            if ((exp & 1) != 0)
                res = (res * base) % mod;
            base = (base * base) % mod;
            exp >>= 1;
        }
        return res;
    }

    static long sumAPrefix(long m) {
        if (m <= 0)
            return 0;
        long pow3 = powMod(3, m + 1, MOD2);
        long num = pow3 - 3;
        if (num < 0)
            num += MOD2;
        long sum3 = num / 2;

        long pow2 = powMod(2, m + 1, MOD);
        long sum2 = pow2 - 2;
        if (sum2 < 0)
            sum2 += MOD;

        long res = sum3 - sum2 - (m % MOD);
        return modNorm(res);
    }

    static class Mertens {
        int limit;
        int[] mu;
        int[] prefix;
        Map<Long, Long> cache;

        Mertens(long n) {
            limit = (int) Math.pow((double) n, 2.0 / 3.0) + 1;
            if (limit < 1)
                limit = 1;
            mu = new int[limit + 1];
            prefix = new int[limit + 1];
            cache = new HashMap<>();
            initMu();
        }

        void initMu() {
            List<Integer> primes = new ArrayList<>();
            byte[] isComp = new byte[limit + 1];
            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;
                    } else {
                        mu[(int) v] = -mu[i];
                    }
                }
            }
            for (int i = 1; i <= limit; ++i) {
                prefix[i] = prefix[i - 1] + mu[i];
            }
        }

        long get(long n) {
            if (n <= limit)
                return prefix[(int) n];
            if (cache.containsKey(n))
                return cache.get(n);
            long res = 1;
            long l = 2;
            while (l <= n) {
                long q = n / l;
                long r = n / q;
                res -= (r - l + 1) * get(q);
                l = r + 1;
            }
            cache.put(n, res);
            return res;
        }
    }

    static long computeTMod(long n) {
        Mertens mertens = new Mertens(n);
        long total = 1 % MOD;
        long l = 1;
        while (l <= n) {
            long q = n / l;
            long r = n / q;
            long sumA = modNorm(sumAPrefix(r) - sumAPrefix(l - 1));
            long mqMod = modNorm(mertens.get(q));
            long contrib = (sumA * mqMod) % MOD;
            total = modNorm(total + contrib);
            l = r + 1;
        }
        return total;
    }

    public static String solve() {
        long n = 10000000000L;
        long ans = computeTMod(n);
        return String.valueOf(ans);
    }

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