import java.util.ArrayList;

public class Euler642 {

    static final long kMod = 1000000000L;

    static long mod_norm(long x) {
        x %= kMod;
        if (x < 0)
            x += kMod;
        return x;
    }

    static long mod_add(long a, long b) {
        a += b;
        if (a >= kMod)
            a -= kMod;
        return a;
    }

    static long mod_sub(long a, long b) {
        a -= b;
        if (a < 0)
            a += kMod;
        return a;
    }

    static long mod_mul(long a, long b) {
        return (a * b) % kMod;
    }

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

    static long sum_2_to_mod(long x) {
        if (x < 2)
            return 0;
        long p1 = x;
        long p2 = x + 1;
        if (p1 % 2 == 0)
            p1 /= 2;
        else
            p2 /= 2;
        p1 %= kMod;
        p2 %= kMod;
        long s = (p1 * p2) % kMod;
        return mod_sub(s, 1);
    }

    static class Solver {
        long n;
        long m;
        long[] pre_cnt;
        long[] pre_sum;
        long[] hou_cnt;
        long[] hou_sum;
        ArrayList<Integer> primes;

        long dfs(long res, int last, int from_prime) {
            long ret = 0;
            if (from_prime > 0) {
                long base = (res > m) ? hou_sum[(int) (n / res)] : pre_sum[(int) res];
                ret = mod_sub(base, pre_sum[primes.get(last) - 1]);
            } else {
                ret = hou_sum[1];
            }

            for (int i = last; i < primes.size(); ++i) {
                long p = primes.get(i);
                if (p * p > res)
                    break;

                long nres = res;
                for (long q = p; q * p <= res; q *= p) {
                    nres /= p;
                    ret = mod_add(ret, dfs(nres, i + 1, (int) p));
                    ret = mod_add(ret, p % kMod);
                }
            }
            return ret;
        }

        long solve(long input_n) {
            n = input_n;
            if (n <= 1)
                return 0;
            m = isqrt(n);

            pre_cnt = new long[(int) (m + 1)];
            pre_sum = new long[(int) (m + 1)];
            hou_cnt = new long[(int) (m + 1)];
            hou_sum = new long[(int) (m + 1)];
            primes = new ArrayList<>((int) (m / 10 + 16));

            for (long i = 1; i <= m; ++i) {
                pre_cnt[(int) i] = i - 1;
                pre_sum[(int) i] = sum_2_to_mod(i);
                long v = n / i;
                hou_cnt[(int) i] = v - 1;
                hou_sum[(int) i] = sum_2_to_mod(v);
            }

            for (long p = 2; p <= m; ++p) {
                if (pre_cnt[(int) p] == pre_cnt[(int) (p - 1)])
                    continue;

                primes.add((int) p);

                long p2 = p * p;
                long q = n / p;
                long p_cnt = pre_cnt[(int) (p - 1)];
                long p_sum = pre_sum[(int) (p - 1)];
                long mid = m / p;
                long end = Math.min(m, n / p2);
                long p_mod = p % kMod;

                for (long i = 1; i <= mid; ++i) {
                    hou_cnt[(int) i] -= (hou_cnt[(int) (i * p)] - p_cnt);
                    hou_sum[(int) i] = mod_sub(hou_sum[(int) i],
                            mod_mul(mod_sub(hou_sum[(int) (i * p)], p_sum), p_mod));
                }
                for (long i = mid + 1; i <= end; ++i) {
                    long qi = q / i;
                    hou_cnt[(int) i] -= (pre_cnt[(int) qi] - p_cnt);
                    hou_sum[(int) i] = mod_sub(hou_sum[(int) i], mod_mul(mod_sub(pre_sum[(int) qi], p_sum), p_mod));
                }
                for (long i = m; i >= p2; --i) {
                    long ip = i / p;
                    pre_cnt[(int) i] -= (pre_cnt[(int) ip] - p_cnt);
                    pre_sum[(int) i] = mod_sub(pre_sum[(int) i], mod_mul(mod_sub(pre_sum[(int) ip], p_sum), p_mod));
                }
            }

            primes.add((int) (m + 1));
            return mod_norm(dfs(n, 0, 0));
        }
    }

    public static String solve() {
        Solver solver = new Solver();
        long ans = solver.solve(201820182018L);
        return Long.toString(ans);
    }

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