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

public class Euler448 {
    static final long MOD = 999999017L;
    static final long DEFAULT_N = 99999999019L;

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

    static long modAdd(long a, long b) {
        long res = a + b;
        if (res >= MOD)
            res -= MOD;
        if (res < 0)
            res += MOD;
        return res;
    }

    static long modSub(long a, long b) {
        long res = a - b;
        if (res < 0)
            res += MOD;
        return res;
    }

    static long egcd(long a, long b, long[] xy) {
        if (b == 0) {
            xy[0] = 1;
            xy[1] = 0;
            return a;
        }
        long[] xy1 = new long[2];
        long g = egcd(b, a % b, xy1);
        xy[0] = xy1[1];
        xy[1] = xy1[0] - xy1[1] * (a / b);
        return g;
    }

    static long modInv(long a) {
        long[] xy = new long[2];
        long g = egcd(a, MOD, xy);
        if (g != 1)
            return 0;
        return modNorm(xy[0]);
    }

    static final long INV2 = (MOD + 1) / 2;
    static final long INV6 = modInv(6);

    static long sumArith(long l, long r) {
        if (l > r)
            return 0;
        long cnt = (r - l + 1) % MOD;
        long s = modNorm(l + r);
        return ((s * cnt) % MOD * INV2) % MOD;
    }

    static long sumSq(long n) {
        n = modNorm(n);
        long a = n;
        long b = modNorm(n + 1);
        long c = modNorm(2 * n + 1);
        return ((((a * b) % MOD) * c) % MOD * INV6) % MOD;
    }

    static class Solver {
        long N;
        int LIM;

        int[] prefH;
        int[] prefG;

        Map<Long, Integer> memoH = new HashMap<>();
        Map<Long, Integer> memoG = new HashMap<>();

        Solver(long n) {
            this.N = n;
            double x = Math.pow(N, 2.0 / 3.0);
            LIM = (int) (x + 10);
            if (LIM < 100)
                LIM = 100;

            sieve();
        }

        void sieve() {
            byte[] mu = new byte[LIM + 1];
            int[] phi = new int[LIM + 1];
            boolean[] isComp = new boolean[LIM + 1];
            List<Integer> primes = new ArrayList<>(LIM / 10);

            mu[1] = 1;
            phi[1] = 1;

            for (int i = 2; i <= LIM; i++) {
                if (!isComp[i]) {
                    primes.add(i);
                    mu[i] = -1;
                    phi[i] = i - 1;
                }
                for (int p : primes) {
                    long v = (long) i * p;
                    if (v > LIM)
                        break;
                    isComp[(int) v] = true;
                    if (i % p == 0) {
                        mu[(int) v] = 0;
                        phi[(int) v] = phi[i] * p;
                        break;
                    }
                    mu[(int) v] = (byte) -mu[i];
                    phi[(int) v] = phi[i] * (p - 1);
                }
            }

            prefH = new int[LIM + 1];
            prefG = new int[LIM + 1];

            long hSum = 0;
            long gSum = 0;

            for (int i = 1; i <= LIM; i++) {
                long addH = 0;
                if (mu[i] == 1) {
                    addH = i;
                } else if (mu[i] == -1) {
                    addH = MOD - i;
                }
                hSum = modAdd(hSum, addH);
                prefH[i] = (int) hSum;

                long addG = ((long) i * phi[i]) % MOD;
                gSum = modAdd(gSum, addG);
                prefG[i] = (int) gSum;
            }
        }

        int H(long n) {
            if (n <= 0)
                return 0;
            if (n <= LIM)
                return prefH[(int) n];
            Integer cached = memoH.get(n);
            if (cached != null)
                return cached;

            long res = 1;
            long l = 2;
            while (l <= n) {
                long v = n / l;
                long r = n / v;
                long coef = sumArith(l, r);
                res = modSub(res, (coef * H(v)) % MOD);
                l = r + 1;
            }

            int out = (int) res;
            memoH.put(n, out);
            return out;
        }

        int G(long n) {
            if (n <= 0)
                return 0;
            if (n <= LIM)
                return prefG[(int) n];
            Integer cached = memoG.get(n);
            if (cached != null)
                return cached;

            long res = 0;
            long l = 1;
            while (l <= n) {
                long v = n / l;
                long r = n / v;
                long muSeg = modSub(H(r), H(l - 1));
                res = modAdd(res, (muSeg * sumSq(v)) % MOD);
                l = r + 1;
            }

            int out = (int) res;
            memoG.put(n, out);
            return out;
        }

        long T(long n) {
            long res = 0;
            long l = 1;
            while (l <= n) {
                long v = n / l;
                long r = n / v;
                long seg = modSub(G(r), G(l - 1));
                res = modAdd(res, ((v % MOD) * seg) % MOD);
                l = r + 1;
            }
            return res;
        }

        long S(long n) {
            long ans = modAdd(modNorm(n), T(n));
            return (ans * INV2) % MOD;
        }
    }

    public static String solve() {
        Solver solver = new Solver(DEFAULT_N);
        return Long.toString(solver.S(DEFAULT_N));
    }

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