import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
import java.util.concurrent.atomic.AtomicInteger;

public class Euler478 {

    private static final long MOD = 214358881L;
    private static final long PHI = 194871710L;
    private static final long PHI2 = 389743420L;

    static class Pow2Mod {
        long mod;
        long[] table = new long[32];

        Pow2Mod(long mod) {
            this.mod = mod;
            table[0] = 2 % mod;
            for (int i = 1; i < 32; i++) {
                table[i] = (table[i - 1] * table[i - 1]) % mod;
            }
        }

        long pow(long exp) {
            long res = 1;
            int bit = 0;
            while (exp > 0) {
                if ((exp & 1) == 1)
                    res = (res * table[bit]) % mod;
                exp >>= 1;
                bit++;
            }
            return res;
        }
    }

    private static void sieveMuPhi(int n, int[] mu, int[] phi) {
        byte[] isComp = new byte[n + 1];
        int[] primes = new int[n + 1]; // Size overhead is fine
        int primeCount = 0;

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

        for (int i = 2; i <= n; i++) {
            if (isComp[i] == 0) {
                primes[primeCount++] = i;
                mu[i] = -1;
                phi[i] = i - 1;
            }
            for (int j = 0; j < primeCount; j++) {
                int p = primes[j];
                long v = (long) i * p;
                if (v > n)
                    break;
                isComp[(int) v] = 1;
                if (i % p == 0) {
                    mu[(int) v] = 0;
                    phi[(int) v] = phi[i] * p;
                    break;
                }
                mu[(int) v] = -mu[i];
                phi[(int) v] = phi[i] * (p - 1);
            }
        }
    }

    private static long countMMod2Phi(int n, int[] mu, int[] nDiv) {
        long total = 0;
        long mertens = 0;
        for (int d = 1; d <= n; d++) {
            int muD = mu[d];
            if (muD == 0)
                continue;
            long k = nDiv[d];
            // BigInteger equivalent for cube
            long rem = (k + 1) % PHI2;
            long term = (rem * rem) % PHI2;
            term = (term * rem) % PHI2;
            // Better to do this correctly without overflow:
            // k+1 <= 10^7, so cube can be 10^21, which overflows long.
            // Using 128-bit or multiple steps with modulo:
            // But PHI2 is ~3.8 * 10^8, so (k+1)^3 mod PHI2 doesn't immediately fit into
            // long multiplication stages implicitly.
            long q1 = ((k + 1) * (k + 1)) % PHI2;
            long q2 = (q1 * ((k + 1) % PHI2)) % PHI2;

            total += (long) muD * q2;
            mertens += muD;
            if (total >= PHI2 || total <= -PHI2)
                total %= PHI2;
            if (mertens >= PHI2 || mertens <= -PHI2)
                mertens %= PHI2;
        }
        total = (total - mertens) % PHI2;
        if (total < 0)
            total += PHI2;
        return total;
    }

    private static long computeE(int n) throws InterruptedException, ExecutionException {
        int[] mu = new int[n + 1];
        int[] phi = new int[n + 1];
        sieveMuPhi(n, mu, phi);

        int[] nDiv = new int[n + 1];
        for (int d = 1; d <= n; d++)
            nDiv[d] = n / d;

        long sumPhiMod = 0;
        for (int i = 1; i <= n; i++) {
            sumPhiMod += phi[i];
            if (sumPhiMod >= MOD)
                sumPhiMod -= MOD;
        }
        long dMod = (6L * sumPhiMod) % MOD;

        long nMod2Phi = countMMod2Phi(n, mu, nDiv);
        long nModPhi = nMod2Phi % PHI;
        long nPrimeMod2Phi = (nMod2Phi + PHI2 - 1) % PHI2;
        if ((nPrimeMod2Phi & 1) != 0) {
            System.err.println("Validation failed: N' not even.");
            return -1;
        }
        long nHalfModPhi = (nPrimeMod2Phi / 2) % PHI;

        Pow2Mod pow2 = new Pow2Mod(MOD);
        long pow2N = pow2.pow(nModPhi);
        long pow2Half = pow2.pow(nHalfModPhi);

        int threads = Math.min(Runtime.getRuntime().availableProcessors(), n);
        if (n < 100000)
            threads = 1;

        AtomicInteger nextL = new AtomicInteger(1);
        int chunk = 64;

        ExecutorService executor = Executors.newFixedThreadPool(threads);
        List<Future<Long>> futures = new ArrayList<>();

        for (int t = 0; t < threads; t++) {
            futures.add(executor.submit(() -> {
                long local = 0;
                while (true) {
                    int start = nextL.getAndAdd(chunk);
                    if (start > n)
                        break;
                    int end = Math.min(n, start + chunk - 1);

                    for (int L = start; L <= end; L++) {
                        int m = n / L;
                        long total = 1;
                        for (int d = 1; d <= m; d++) {
                            int muD = mu[d];
                            if (muD == 0)
                                continue;
                            int md = m / d;
                            long term = 1L * md * nDiv[d] - 1L * L * md * (md + 1) / 2;
                            total += (long) muD * term;
                        }
                        long gMod = total % PHI;
                        if (gMod < 0)
                            gMod += PHI;
                        long exp = nHalfModPhi - gMod;
                        if (exp < 0)
                            exp += PHI;
                        long p2 = pow2.pow(exp);
                        long mL = (6L * phi[L]) % MOD;
                        local += (mL * p2) % MOD;
                        if (local >= MOD)
                            local %= MOD;
                    }
                }
                return local % MOD;
            }));
        }

        long s = 0;
        for (Future<Long> f : futures) {
            s += f.get();
            if (s >= MOD)
                s %= MOD;
        }
        executor.shutdown();

        long f = (1 + (pow2Half * dMod) % MOD - s) % MOD;
        if (f < 0)
            f += MOD;
        long e = (pow2N - f) % MOD;
        if (e < 0)
            e += MOD;
        return e;
    }

    public static void main(String[] args) throws Exception {
        int n = 10_000_000;
        System.out.println(computeE(n));
    }
}