public class Euler875 {

    static final int LIMIT = 12345678;
    static final long MOD = 1001961001L;

    static long qPrimePowerMod(int p, int e) {
        if (e == 0)
            return 1;

        if (p == 2) {
            long q = 128 % MOD;
            long add = 2048 % MOD;
            for (int k = 2; k <= e; ++k) {
                q = (q * 128L + add) % MOD;
                add = (add * 16L) % MOD;
            }
            return q;
        }

        long pm = (p % MOD + MOD) % MOD;
        long p2 = (pm * pm) % MOD;
        long p3 = (p2 * pm) % MOD;
        long p4 = (p2 * p2) % MOD;
        long p7 = (p4 * p3) % MOD;
        long coeff = (pm + MOD - 1) % MOD;

        long q = 1;
        long term = p3;
        for (int k = 1; k <= e; ++k) {
            q = (q * p7 + coeff * term) % MOD;
            term = (term * p4) % MOD;
        }
        return q;
    }

    static long computeQMod(int n) {
        int[] spf = new int[n + 1];
        int[] primes = new int[n / 10 + 1000];
        int numPrimes = 0;

        for (int i = 2; i <= n; ++i) {
            if (spf[i] == 0) {
                spf[i] = i;
                if (numPrimes == primes.length) {
                    int[] newPrimes = new int[primes.length * 2];
                    System.arraycopy(primes, 0, newPrimes, 0, primes.length);
                    primes = newPrimes;
                }
                primes[numPrimes++] = i;
            }
            for (int j = 0; j < numPrimes; ++j) {
                int p = primes[j];
                long v = (long) p * i;
                if (v > n)
                    break;
                spf[(int) v] = p;
                if (p == spf[i])
                    break;
            }
        }

        long sum = 1;
        for (int i = 2; i <= n; ++i) {
            int x = i;
            long qn = 1;
            while (x > 1) {
                int p = spf[x];
                int e = 0;
                while (x > 1 && spf[x] == p) {
                    x /= p;
                    ++e;
                }
                qn = (qn * qPrimePowerMod(p, e)) % MOD;
            }
            sum += qn;
            if (sum >= MOD)
                sum -= MOD;
        }

        return sum;
    }

    public static String solve() {
        return Long.toString(computeQMod(LIMIT));
    }

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