import java.util.ArrayList;

public class Euler802 {
    static final long MOD = 1020340567L;

    public static String solve(int N) {
        int[] lp = new int[N + 1];
        ArrayList<Integer> primes = new ArrayList<>();
        byte[] mu = new byte[N + 1];
        mu[1] = 1;

        for (int i = 2; i <= N; ++i) {
            if (lp[i] == 0) {
                lp[i] = i;
                primes.add(i);
                mu[i] = -1;
            }
            for (int p : primes) {
                long v = (long) i * p;
                if (v > N) {
                    break;
                }
                lp[(int) v] = p;
                if (p == lp[i]) {
                    mu[(int) v] = 0;
                    break;
                }
                mu[(int) v] = (byte) -mu[i];
            }
        }

        int[] prefMu = new int[N + 1];
        for (int i = 1; i <= N; ++i) {
            prefMu[i] = prefMu[i - 1] + mu[i];
        }

        long[] pow2 = new long[N + 1];
        pow2[0] = 1;
        for (int i = 1; i <= N; ++i) {
            pow2[i] = (pow2[i - 1] * 2L) % MOD;
        }

        long ans = 0;
        int i = 1;
        while (i <= N) {
            int q = N / i;
            int j = N / q;

            long blockMu = prefMu[j] - prefMu[i - 1];
            long term = blockMu % MOD;

            ans = (ans + term * pow2[q]) % MOD;

            i = j + 1;
        }

        if (ans < 0) {
            ans += MOD;
        }
        return Long.toString(ans);
    }

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