import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.LinkedList;

public class Euler823 {

    static final long kMod = 1234567891L;

    static int[] sieveSpf(int n) {
        int[] spf = new int[n + 1];
        for (int i = 0; i <= n; ++i) {
            spf[i] = i;
        }
        int lim = (int) Math.sqrt(n);
        for (int i = 2; i <= lim; ++i) {
            if (spf[i] == i) {
                for (int j = i * i; j <= n; j += i) {
                    if (spf[j] == j) {
                        spf[j] = i;
                    }
                }
            }
        }
        return spf;
    }

    static ArrayList<Integer> factorList(int x, int[] spf) {
        ArrayList<Integer> out = new ArrayList<>();
        while (x > 1) {
            int p = spf[x];
            out.add(p);
            x /= p;
        }
        return out;
    }

    static class SimResult {
        long endT;
        ArrayList<ArrayList<Integer>> patterns;
        int kmax;

        SimResult(long endT, ArrayList<ArrayList<Integer>> patterns, int kmax) {
            this.endT = endT;
            this.patterns = patterns;
            this.kmax = kmax;
        }
    }

    static long directSumMod(int n, long m, long mod) {
        int[] spf = sieveSpf(n);
        ArrayList<ArrayList<Integer>> piles = new ArrayList<>(n);
        ArrayList<Integer> pos = new ArrayList<>(n);

        for (int i = 2; i <= n; ++i) {
            piles.add(factorList(i, spf));
            pos.add(0);
        }

        for (long t = 0; t < m; ++t) {
            int k = piles.size();
            ArrayList<Integer> extracted = new ArrayList<>(k);
            ArrayList<ArrayList<Integer>> nextPiles = new ArrayList<>(k + 1);
            ArrayList<Integer> nextPos = new ArrayList<>(k + 1);

            for (int i = 0; i < k; ++i) {
                int pIdx = pos.get(i);
                extracted.add(piles.get(i).get(pIdx));
                pos.set(i, pIdx + 1);
                if (pos.get(i) < piles.get(i).size()) {
                    nextPiles.add(piles.get(i));
                    nextPos.add(pos.get(i));
                }
            }

            Collections.sort(extracted);
            nextPiles.add(extracted);
            nextPos.add(0);

            piles = nextPiles;
            pos = nextPos;
        }

        long total = 0;
        for (int i = 0; i < piles.size(); ++i) {
            long prod = 1;
            for (int j = pos.get(i); j < piles.get(i).size(); ++j) {
                prod = (prod * piles.get(i).get(j)) % mod;
            }
            total += prod;
            if (total >= mod) {
                total -= mod;
            }
        }
        return total;
    }

    static SimResult simulateUntilPeriodic(int n, int kExtra, int streakNeeded, int maxRounds) {
        int[] spf = sieveSpf(n);

        ArrayList<ArrayList<Integer>> piles = new ArrayList<>(n);
        ArrayList<Integer> pos = new ArrayList<>(n);

        long totalFactors = 0;
        for (int i = 2; i <= n; ++i) {
            ArrayList<Integer> f = factorList(i, spf);
            totalFactors += f.size();
            piles.add(f);
            pos.add(0);
        }

        int kLim = (int) Math.sqrt(2.0 * totalFactors) + kExtra;
        ArrayList<Deque<Integer>> bufs = new ArrayList<>(kLim + 1);
        for (int i = 0; i <= kLim; i++) {
            bufs.add(new LinkedList<>());
        }

        int stableStreak = 0;

        for (int t = 1; t <= maxRounds; ++t) {
            int k = piles.size();
            ArrayList<Integer> extracted = new ArrayList<>(k);
            ArrayList<ArrayList<Integer>> nextPiles = new ArrayList<>(k + 1);
            ArrayList<Integer> nextPos = new ArrayList<>(k + 1);

            for (int i = 0; i < k; ++i) {
                int pIdx = pos.get(i);
                extracted.add(piles.get(i).get(pIdx));
                pos.set(i, pIdx + 1);
                if (pos.get(i) < piles.get(i).size()) {
                    nextPiles.add(piles.get(i));
                    nextPos.add(pos.get(i));
                }
            }

            Collections.sort(extracted);
            nextPiles.add(extracted);
            nextPos.add(0);

            piles = nextPiles;
            pos = nextPos;

            int mm = Math.min(extracted.size(), kLim);

            if (t <= kLim) {
                for (int kk = 1; kk <= mm; ++kk) {
                    Deque<Integer> b = bufs.get(kk);
                    b.addLast(extracted.get(kk - 1));
                    if (b.size() > kk)
                        b.removeFirst();
                }
                for (int kk = mm + 1; kk <= kLim; ++kk) {
                    Deque<Integer> b = bufs.get(kk);
                    b.addLast(1);
                    if (b.size() > kk)
                        b.removeFirst();
                }
                stableStreak = 0;
                continue;
            }

            boolean allOk = true;

            for (int kk = 1; kk <= mm; ++kk) {
                Deque<Integer> b = bufs.get(kk);
                int v = extracted.get(kk - 1);
                if (b.peekFirst() != v) {
                    allOk = false;
                }
                b.addLast(v);
                if (b.size() > kk)
                    b.removeFirst();
            }

            for (int kk = mm + 1; kk <= kLim; ++kk) {
                Deque<Integer> b = bufs.get(kk);
                if (b.peekFirst() != 1) {
                    allOk = false;
                }
                b.addLast(1);
                if (b.size() > kk)
                    b.removeFirst();
            }

            if (allOk) {
                stableStreak++;
                if (stableStreak >= streakNeeded) {
                    ArrayList<ArrayList<Integer>> patterns = new ArrayList<>(kLim + 1);
                    for (int i = 0; i <= kLim; i++)
                        patterns.add(new ArrayList<>());

                    int kmax = 0;
                    for (int kk = 1; kk <= kLim; ++kk) {
                        ArrayList<Integer> pat = new ArrayList<>(bufs.get(kk));
                        patterns.set(kk, pat);
                        boolean hasNonOne = false;
                        for (int x : pat) {
                            if (x != 1) {
                                hasNonOne = true;
                                break;
                            }
                        }
                        if (hasNonOne) {
                            kmax = kk;
                        }
                    }
                    return new SimResult(t, patterns, kmax);
                }
            } else {
                stableStreak = 0;
            }
        }

        throw new RuntimeException("periodicity not detected");
    }

    static long sumAtRoundMod(int n, long m, long mod) {
        SimResult sim = simulateUntilPeriodic(n, 10, 2000, 200000);

        if (m <= sim.endT) {
            return directSumMod(n, m, mod);
        }

        long r0 = m - sim.endT - 1;
        long total = 0;

        for (int d = 0; d < sim.kmax; ++d) {
            long r = r0 - d;
            int patIndex = (int) (r % (d + 1));
            if (patIndex < 0)
                patIndex += (d + 1); // just in case

            if (sim.patterns.get(d + 1).get(patIndex) == 1) {
                continue;
            }

            long prod = 1;
            for (int k = sim.kmax; k > d; --k) {
                int innerIndex = (int) (r % k);
                if (innerIndex < 0)
                    innerIndex += k;
                int v = sim.patterns.get(k).get(innerIndex);
                if (v != 1) {
                    prod = (prod * v) % mod;
                }
            }

            total += prod;
            if (total >= mod) {
                total -= mod;
            }
        }

        return total;
    }

    public static String solve() {
        return Long.toString(sumAtRoundMod(10000, 10000000000000000L, kMod));
    }

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