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

public class Euler915 {

    static final long MOD = 123456789L;

    static long nextValue(long x, long mod) {
        long y = x == 0 ? mod - 1 : x - 1;
        long y2 = (y * y) % mod;
        long y3 = (y2 * y) % mod;
        long z = y3 + 2;
        if (z >= mod) {
            z -= mod;
        }
        return z;
    }

    static long[] cycleMuLambda(long mod) {
        long tortoise = nextValue(1, mod);
        long hare = nextValue(nextValue(1, mod), mod);

        while (tortoise != hare) {
            tortoise = nextValue(tortoise, mod);
            hare = nextValue(nextValue(hare, mod), mod);
        }

        long mu = 0;
        tortoise = 1;
        while (tortoise != hare) {
            tortoise = nextValue(tortoise, mod);
            hare = nextValue(hare, mod);
            ++mu;
        }

        long lambda = 1;
        hare = nextValue(tortoise, mod);
        while (tortoise != hare) {
            hare = nextValue(hare, mod);
            ++lambda;
        }

        return new long[] { mu, lambda };
    }

    static class Group {
        int l;
        int r;
        int q;

        Group(int l, int r, int q) {
            this.l = l;
            this.r = r;
            this.q = q;
        }
    }

    static class SumPhi {
        int limit;
        long[] prefix;
        Map<Long, Long> memo = new HashMap<>();

        SumPhi(int n) {
            int kBase = 1000000;
            limit = n < kBase ? n : kBase;

            int[] lp = new int[limit + 1];
            int[] phi = new int[limit + 1];
            phi[1] = 1;

            List<Integer> primes = new ArrayList<>();
            for (int i = 2; i <= limit; ++i) {
                if (lp[i] == 0) {
                    lp[i] = i;
                    primes.add(i);
                    phi[i] = i - 1;
                }
                for (int p : primes) {
                    long v = (long) i * p;
                    if (v > limit || p > lp[i]) {
                        break;
                    }
                    lp[(int) v] = p;
                    if (i % p == 0) {
                        phi[(int) v] = phi[i] * p;
                        break;
                    }
                    phi[(int) v] = phi[i] * (p - 1);
                }
            }

            prefix = new long[limit + 1];
            for (int i = 1; i <= limit; ++i) {
                prefix[i] = prefix[i - 1] + phi[i];
            }
        }

        long get(long n) {
            if (n <= limit) {
                return prefix[(int) n];
            }
            if (memo.containsKey(n)) {
                return memo.get(n);
            }

            long ans = n % 2 == 0 ? (n / 2) * (n + 1) : n * ((n + 1) / 2);
            for (long l = 2; l <= n;) {
                long q = n / l;
                long r = n / q;
                long cnt = r - l + 1;
                ans -= cnt * get(q);
                l = r + 1;
            }
            memo.put(n, ans);
            return ans;
        }
    }

    public static String solve() {
        int N = 100000000;
        long[] muLambda = cycleMuLambda(MOD);
        long mu0 = muLambda[0];
        long lambda = muLambda[1];
        long cycleStart = mu0 + 1;

        int need = (int) (cycleStart + lambda);
        int[] sMod = new int[need + 1];
        sMod[1] = 1;
        for (int i = 2; i <= need; ++i) {
            sMod[i] = (int) nextValue(sMod[i - 1], MOD);
        }

        List<Group> groups = new ArrayList<>();
        for (int l = 1; l <= N;) {
            int q = N / l;
            int r = N / q;
            groups.add(new Group(l, r, q));
            l = r + 1;
        }

        SumPhi sumPhi = new SumPhi(N);

        long answer = 0;
        long prefUMod = 0;
        long prevPrefUMod = 0;

        int d = 1;
        long sDModLambda = 1 % lambda;

        long[] smallIndex = { 0, 1, 2, 3, 10 };

        for (Group g : groups) {
            while (d <= g.r) {
                long uD;
                if (d <= 4) {
                    uD = sMod[(int) smallIndex[d]];
                } else {
                    long startMod = cycleStart % lambda;
                    long delta = (sDModLambda + lambda - startMod) % lambda;
                    long idx = cycleStart + delta;
                    uD = sMod[(int) idx];
                }

                prefUMod += uD;
                prefUMod %= MOD;

                sDModLambda = nextValue(sDModLambda, lambda);
                ++d;
            }

            long segment = prefUMod - prevPrefUMod;
            segment %= MOD;
            if (segment < 0) {
                segment += MOD;
            }

            long sp = sumPhi.get(g.q) % MOD;
            long cmod = (2L * sp + MOD - 1L) % MOD;
            answer += segment * cmod % MOD;
            answer %= MOD;

            prevPrefUMod = prefUMod;
        }

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

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