import java.util.ArrayList;
import java.util.List;

public class Euler468 {

    static final long MOD = 1000000993L;

    static long mulMod(long a, long b) {
        return (a * b) % MOD;
    }

    static long modPow(long base, long exponent) {
        long result = 1;
        long b = base % MOD;
        long e = exponent;
        while (e > 0) {
            if ((e & 1) != 0) {
                result = mulMod(result, b);
            }
            b = mulMod(b, b);
            e >>= 1;
        }
        return result;
    }

    static class SegmentTree {
        int leafCount;
        int size;
        long[] prod;
        long[] sum;

        SegmentTree(int[] weights) {
            leafCount = weights.length;
            size = 1;
            while (size < leafCount) {
                size <<= 1;
            }
            prod = new long[2 * size];
            sum = new long[2 * size];
            for (int i = 0; i < 2 * size; i++)
                prod[i] = 1;
            for (int i = 0; i < 2 * size; i++)
                sum[i] = 0;

            for (int i = 0; i < leafCount; i++) {
                sum[size + i] = weights[i] % MOD;
            }

            for (int node = size - 1; node >= 1; node--) {
                pull(node);
            }
        }

        void pull(int node) {
            int left = node << 1;
            int right = left | 1;
            prod[node] = mulMod(prod[left], prod[right]);
            sum[node] = (sum[left] + mulMod(prod[left], sum[right])) % MOD;
        }

        void multiplyLeaf(int leafIndex, long factor) {
            int node = size + leafIndex;
            prod[node] = mulMod(prod[node], factor);
            sum[node] = mulMod(sum[node], factor);

            for (node >>= 1; node > 0; node >>= 1) {
                pull(node);
            }
        }

        long rootSum() {
            return sum[1];
        }
    }

    static class SieveData {
        int n;
        int[] weights;
        int[] stripNext;
        int[] stripPos;
        long[] stripMul;
        long[] stripInv;
    }

    static SieveData buildSieveData(int n) {
        SieveData data = new SieveData();
        data.n = n;
        int[] spf = new int[n + 1];
        int[] primePos = new int[n + 1];
        for (int i = 0; i <= n; i++)
            primePos[i] = -1;

        List<Integer> primes = new ArrayList<>(n / 10);
        for (int i = 2; i <= n; i++) {
            if (spf[i] == 0) {
                spf[i] = i;
                primes.add(i);
            }
            for (int p : primes) {
                long composite = (long) i * p;
                if (composite > n)
                    break;
                spf[(int) composite] = p;
                if (p == spf[i])
                    break;
            }
        }

        int pCount = primes.size();
        long[] invPrimeByPos = new long[pCount];
        data.weights = new int[pCount];
        for (int i = 0; i < pCount; i++) {
            int p = primes.get(i);
            primePos[p] = i;
            invPrimeByPos[i] = modPow(p, MOD - 2);
            int nextPrime = (i + 1 < pCount) ? primes.get(i + 1) : (n + 1);
            data.weights[i] = nextPrime - p;
        }

        data.stripNext = new int[n + 1];
        data.stripPos = new int[n + 1];
        data.stripMul = new long[n + 1];
        data.stripInv = new long[n + 1];

        for (int x = 2; x <= n; x++) {
            int p = spf[x];
            int pos = primePos[p];
            long invP = invPrimeByPos[pos];

            int value = x;
            long mul = 1;
            long invMul = 1;
            do {
                value /= p;
                mul = mulMod(mul, p);
                invMul = mulMod(invMul, invP);
            } while (value % p == 0);

            data.stripNext[x] = value;
            data.stripPos[x] = pos;
            data.stripMul[x] = mul;
            data.stripInv[x] = invMul;
        }

        return data;
    }

    public static String solve() {
        int n = 11111111;
        SieveData data = buildSieveData(n);
        SegmentTree tree = new SegmentTree(data.weights);

        long total = 0;
        int half = n / 2;
        int r = 0;

        int[] positions = new int[16];
        long[] factors = new long[16];

        while (true) {
            long v = tree.rootSum();
            long contribution = (v + 1 == MOD) ? 0 : (v + 1);

            if (r == n - r) {
                total = (total + contribution) % MOD;
            } else {
                total = (total + contribution * 2) % MOD;
            }

            if (r == half)
                break;

            int used = 0;
            int val = n - r;
            while (val > 1) {
                int pos = data.stripPos[val];
                long factor = data.stripMul[val];
                int slot = -1;
                for (int i = 0; i < used; i++) {
                    if (positions[i] == pos) {
                        slot = i;
                        break;
                    }
                }
                if (slot < 0) {
                    positions[used] = pos;
                    factors[used] = factor;
                    used++;
                } else {
                    factors[slot] = mulMod(factors[slot], factor);
                }
                val = data.stripNext[val];
            }

            val = r + 1;
            while (val > 1) {
                int pos = data.stripPos[val];
                long factor = data.stripInv[val];
                int slot = -1;
                for (int i = 0; i < used; i++) {
                    if (positions[i] == pos) {
                        slot = i;
                        break;
                    }
                }
                if (slot < 0) {
                    positions[used] = pos;
                    factors[used] = factor;
                    used++;
                } else {
                    factors[slot] = mulMod(factors[slot], factor);
                }
                val = data.stripNext[val];
            }

            for (int i = 0; i < used; i++) {
                if (factors[i] != 1) {
                    tree.multiplyLeaf(positions[i], factors[i]);
                }
            }
            r++;
        }

        return Long.toString(total);
    }

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