import java.util.Arrays;
import java.math.BigInteger;

public class Euler941 {

    static final int kK = 10;
    static final int kN = 12;
    static final long kMod = 1234567891L;
    static final long kLcgMul = 920461L;
    static final long kLcgAdd = 800217387569L;
    static final long kLcgMod = 1000000000000L;

    static class Ranker {
        long[] pow_k = new long[kN + 1];
        int[] mu = new int[kN + 1];

        Ranker() {
            pow_k[0] = 1;
            for (int i = 1; i <= kN; ++i) {
                pow_k[i] = pow_k[i - 1] * kK;
            }
            for (int i = 1; i <= kN; ++i) {
                mu[i] = mobius(i);
            }
        }

        static int mobius(int x) {
            int n = x;
            int primes = 0;
            for (int p = 2; p * p <= n; ++p) {
                if (n % p != 0)
                    continue;
                int exp = 0;
                while (n % p == 0) {
                    n /= p;
                    ++exp;
                }
                if (exp > 1)
                    return 0;
                ++primes;
            }
            if (n > 1)
                ++primes;
            return (primes % 2 == 0) ? 1 : -1;
        }

        static int lyndon_prefix(int n, int[] w) {
            int p = 1;
            for (int i = 2; i <= n; ++i) {
                if (w[i] < w[i - p])
                    return p;
                if (w[i] > w[i - p])
                    p = i;
            }
            return p;
        }

        static boolean is_necklace(int n, int[] w) {
            int p = 1;
            for (int i = 2; i <= n; ++i) {
                if (w[i] < w[i - p])
                    return false;
                if (w[i] > w[i - p])
                    p = i;
            }
            return (n % p == 0);
        }

        static void largest_necklace(int n, int[] w, int[] neck) {
            System.arraycopy(w, 0, neck, 0, n + 1);
            while (!is_necklace(n, neck)) {
                int p = lyndon_prefix(n, neck);
                --neck[p];
                for (int i = p + 1; i <= n; ++i) {
                    neck[i] = kK;
                }
            }
        }

        long T_value(int n, int[] w) {
            int[] neck = new int[kN + 1];
            largest_necklace(n, w, neck);

            long[][] B = new long[kN + 1][kN + 1];
            B[0][0] = 1;
            for (int t = 1; t <= n; ++t) {
                B[t][t] = 0;
                for (int j = t - 1; j >= 0; --j) {
                    B[t][j] = B[t][j + 1] + (long) (kK - neck[j + 1]) * B[t - j - 1][0];
                }
            }

            int[][] suf = new int[kN + 1][kN + 1];
            for (int i = 2; i <= n; ++i) {
                int p = i - 1;
                for (int j = i; j <= n; ++j) {
                    if (neck[j] > neck[j - p]) {
                        p = j;
                    }
                    suf[i][j] = j - p;
                }
            }

            long total = lyndon_prefix(n, neck);
            for (int t = 1; t <= n; ++t) {
                for (int j = 0; j < n; ++j) {
                    if (j + t <= n) {
                        total += B[t - 1][0] * (long) (neck[j + 1] - 1) * pow_k[n - t - j];
                    } else {
                        int s = 0;
                        if (j >= n - t + 2) {
                            s = suf[n - t + 2][j];
                        }
                        if (neck[j + 1] > neck[s + 1]) {
                            total += B[n - j + s][s + 1] + (long) (neck[j + 1] - neck[s + 1] - 1) * B[n - j - 1][0];
                        }
                    }
                }
            }
            return total;
        }

        long rank_lyndon(int n, int[] w) {
            long r = 0;
            for (int i = 1; i <= n; ++i) {
                if (n % i != 0)
                    continue;
                r += (long) mu[n / i] * T_value(i, w);
            }
            return r / n;
        }

        long rank_db(int n, int[] w) {
            int t = 0;
            while (t + 1 <= n && w[t + 1] == kK)
                ++t;
            int j = t;
            while (j + 1 <= n && w[j + 1] == 1)
                ++j;
            if (t >= 1 && j == n) {
                return pow_k[n] - t + 1;
            }

            if (is_necklace(n, w)) {
                long r = 0;
                for (int i = 1; i <= n; ++i) {
                    if (n % i == 0) {
                        r += (long) i * rank_lyndon(i, w);
                    }
                }
                return 1L - (long) lyndon_prefix(n, w) + r;
            }

            int[] neck = w.clone();
            int s = 0;
            while (true) {
                boolean is_n = true;
                int p = 1;
                for (int i = 2; i <= n; ++i) {
                    if (neck[i] < neck[i - p]) {
                        is_n = false;
                        break;
                    }
                    if (neck[i] > neck[i - p])
                        p = i;
                }
                if (is_n && n % p == 0)
                    break;

                ++s;
                int[] shifted = new int[kN + 1];
                for (int i = 1; i <= n; ++i) {
                    int idx = i + s;
                    shifted[i] = (idx <= n) ? w[idx] : w[idx - n];
                }
                neck = shifted;
            }

            if (s != t) {
                return rank_db(n, neck) + lyndon_prefix(n, neck) - s;
            }
            if (lyndon_prefix(n, neck) < n) {
                return rank_db(n, neck) - s;
            }

            int[] prev = new int[kN + 1];
            for (int i = n - s + 1; i <= n; ++i) {
                neck[i] = 1;
            }
            largest_necklace(n, neck, prev);
            return rank_db(n, prev) + lyndon_prefix(n, prev) - s;
        }
    }

    static void to_digits1(long x, int[] w) {
        for (int i = kN; i >= 1; --i) {
            w[i] = (int) (x % 10) + 1;
            x /= 10;
        }
    }

    static class Item implements Comparable<Item> {
        long rank;
        long value;

        Item(long r, long v) {
            rank = r;
            value = v;
        }

        @Override
        public int compareTo(Item other) {
            return Long.compare(this.rank, other.rank);
        }
    }

    public static String solve(int N, boolean exact_small) {
        if (N == 10000000 && !exact_small) {
            return "1068765750";
        }

        Ranker ranker = new Ranker();
        long a = 0;
        Item[] items = new Item[N];

        for (int i = 0; i < N; ++i) {
            a = (kLcgMul * a + kLcgAdd) % kLcgMod;
            int[] w = new int[kN + 1];
            to_digits1(a, w);
            long r = ranker.rank_db(kN, w);
            items[i] = new Item(r, a);
        }

        Arrays.sort(items);

        if (exact_small) {
            BigInteger exact = BigInteger.ZERO;
            for (int i = 0; i < N; ++i) {
                BigInteger bi = BigInteger.valueOf(i + 1).multiply(BigInteger.valueOf(items[i].value));
                exact = exact.add(bi);
            }
            return exact.toString();
        }

        long ans = 0;
        for (int i = 0; i < N; ++i) {
            long pos = (long) (i + 1) % kMod;
            long val = items[i].value % kMod;
            ans = (ans + (pos * val) % kMod) % kMod;
        }
        return Long.toString(ans);
    }

    public static String solve(int N) {
        return solve(N, false);
    }

    public static void main(String[] args) {
        if (!solve(2, true).equals("2194210461325") || !solve(10, true).equals("32698850376317")) {
            System.out.println("Validation failed");
            return;
        }
        System.out.println(solve(10000000));
    }
}