import java.util.Arrays;
import java.util.HashSet;
import java.util.Objects;
import java.util.Set;

public class Euler996 {
    static final int TARGET_N = 123;
    static final long TARGET_K = 4_567_891L;
    static final long TARGET_E = TARGET_K / 2;
    static final long MOD = 1_234_567_891L;

    static long[][] binomialTable(int n, int r, long mod) {
        long[][] c = new long[n + 1][r + 1];
        c[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            c[i][0] = 1;
            int hi = Math.min(i, r);
            for (int j = 1; j <= hi; j++) {
                long value = c[i - 1][j - 1] + c[i - 1][j];
                c[i][j] = mod == 0 ? value : value % mod;
            }
        }
        return c;
    }

    static long chooseFromTable(long[][] c, int n, int r) {
        if (n < 0 || r < 0 || n < r) {
            return 0;
        }
        if (n >= c.length || r >= c[0].length) {
            return 0;
        }
        return c[n][r];
    }

    static long[][] runCountTable(int n, int emax, long mod) {
        long[][] comb = binomialTable(2 * emax + 1, n, mod);
        long[][] runs = new long[n + 1][emax + 1];

        for (int length = 2; length <= n; length++) {
            for (int e = 1; e <= emax; e++) {
                long allPositive = chooseFromTable(comb, 2 * e - 1, length - 1);
                long tooLarge = chooseFromTable(comb, e - 1, length - 1);
                if (mod == 0) {
                    runs[length][e] = allPositive - (long) length * tooLarge;
                } else {
                    runs[length][e] = Math.floorMod(allPositive - (long) length * tooLarge, mod);
                }
            }
        }
        return runs;
    }

    static long[] cumulativeCounts(int n, int emax, long mod) {
        long[][] runs = runCountTable(n, emax, mod);
        long[][] total = new long[n + 1][emax + 1];
        long[][] zero = new long[n + 1][emax + 1];
        total[0][0] = 1;
        zero[0][0] = 1;

        for (int i = 1; i <= n; i++) {
            zero[i] = Arrays.copyOf(total[i - 1], emax + 1);
            long[] row = Arrays.copyOf(zero[i], emax + 1);

            for (int length = 2; length <= i; length++) {
                long[] source = zero[i - length];
                long[] run = runs[length];
                for (int before = 0; before <= emax; before++) {
                    long sourceValue = source[before];
                    if (sourceValue == 0) {
                        continue;
                    }
                    for (int used = 1; before + used <= emax; used++) {
                        long runValue = run[used];
                        if (runValue == 0) {
                            continue;
                        }
                        if (mod == 0) {
                            row[before + used] += sourceValue * runValue;
                        } else {
                            row[before + used] = (row[before + used] + sourceValue * runValue) % mod;
                        }
                    }
                }
            }

            total[i] = row;
        }

        long[] cumulative = new long[emax + 1];
        long sum = 0;
        for (int e = 0; e <= emax; e++) {
            sum += total[n][e];
            if (mod != 0) {
                sum %= mod;
            }
            cumulative[e] = sum;
        }
        return cumulative;
    }

    static long gcd(long a, long b) {
        while (b != 0) {
            long t = a % b;
            a = b;
            b = t;
        }
        return Math.abs(a);
    }

    static long binomialLargeMod(long n, int r) {
        if (r < 0 || n < r) {
            return 0;
        }
        if ((long) r > n - r) {
            r = (int) (n - r);
        }

        long[] numerator = new long[r];
        for (int i = 0; i < r; i++) {
            numerator[i] = n - r + 1L + i;
        }

        for (int d = 2; d <= r; d++) {
            long remaining = d;
            for (int i = 0; i < numerator.length; i++) {
                long g = gcd(numerator[i], remaining);
                if (g == 1) {
                    continue;
                }
                numerator[i] /= g;
                remaining /= g;
                if (remaining == 1) {
                    break;
                }
            }
            assert remaining == 1;
        }

        long result = 1;
        for (long value : numerator) {
            result = result * (value % MOD) % MOD;
        }
        return result;
    }

    static long polynomialTailValue(int n, long e) {
        int start = n - 1;
        int degree = n;
        int emax = start + degree;
        long[] cumulative = cumulativeCounts(n, emax, MOD);

        long[] current = new long[degree + 1];
        for (int i = 0; i <= degree; i++) {
            current[i] = cumulative[start + i];
        }

        long[] differences = new long[degree + 1];
        for (int r = 0; r <= degree; r++) {
            differences[r] = current[0];
            long[] next = new long[current.length - 1];
            for (int i = 0; i + 1 < current.length; i++) {
                next[i] = Math.floorMod(current[i + 1] - current[i], MOD);
            }
            current = next;
        }

        long x = e - start;
        long result = 0;
        for (int r = 0; r <= degree; r++) {
            result = (result + differences[r] * binomialLargeMod(x, r)) % MOD;
        }
        return result;
    }

    static long bruteCount(int n, int emax) {
        int[] identityArray = new int[n];
        for (int i = 0; i < n; i++) {
            identityArray[i] = i;
        }
        IntVector identity = new IntVector(identityArray);

        Set<State> states = new HashSet<>();
        states.add(new State(identity, new IntVector(new int[n])));

        Set<IntVector> results = new HashSet<>();
        results.add(new IntVector(new int[n]));

        for (int step = 1; step <= 2 * emax; step++) {
            Set<State> next = new HashSet<>();
            for (State state : states) {
                for (int p = 0; p + 1 < n; p++) {
                    int[] nextPerm = state.perm.values.clone();
                    int[] nextCount = state.count.values.clone();
                    nextCount[nextPerm[p + 1]]++;
                    int temp = nextPerm[p];
                    nextPerm[p] = nextPerm[p + 1];
                    nextPerm[p + 1] = temp;

                    IntVector permVector = new IntVector(nextPerm);
                    IntVector countVector = new IntVector(nextCount);
                    if (permVector.equals(identity)) {
                        results.add(countVector);
                    }
                    next.add(new State(permVector, countVector));
                }
            }
            states = next;
        }
        return results.size();
    }

    static void runCheckpoints() {
        for (int n = 2; n <= 5; n++) {
            long[] values = cumulativeCounts(n, 4, 0);
            for (int e = 0; e <= 4; e++) {
                assert values[e] == bruteCount(n, e);
            }
        }

        assert cumulativeCounts(3, 2, 0)[2] == 8;
        assert cumulativeCounts(12, 17, 0)[17] == 2_457_178_250L;

        for (int n = 2; n <= 8; n++) {
            int start = n - 1;
            int degree = n;
            int emax = start + degree + 5;
            long[] values = cumulativeCounts(n, emax, 0);

            long[] current = new long[degree + 1];
            for (int i = 0; i <= degree; i++) {
                current[i] = values[start + i];
            }

            long[] differences = new long[degree + 1];
            for (int r = 0; r <= degree; r++) {
                differences[r] = current[0];
                long[] next = new long[current.length - 1];
                for (int i = 0; i + 1 < current.length; i++) {
                    next[i] = current[i + 1] - current[i];
                }
                current = next;
            }

            for (int e = start; e <= emax; e++) {
                long predicted = 0;
                long choose = 1;
                for (int r = 0; r <= degree; r++) {
                    if (r > 0) {
                        choose = choose * (e - start - r + 1L) / r;
                    }
                    predicted += differences[r] * choose;
                }
                assert predicted == values[e];
            }
        }
    }

    public static void main(String[] args) {
        runCheckpoints();
        System.out.println(polynomialTailValue(TARGET_N, TARGET_E));
    }

    static final class IntVector {
        final int[] values;

        IntVector(int[] values) {
            this.values = values;
        }

        @Override
        public boolean equals(Object other) {
            return other instanceof IntVector && Arrays.equals(values, ((IntVector) other).values);
        }

        @Override
        public int hashCode() {
            return Arrays.hashCode(values);
        }
    }

    static final class State {
        final IntVector perm;
        final IntVector count;

        State(IntVector perm, IntVector count) {
            this.perm = perm;
            this.count = count;
        }

        @Override
        public boolean equals(Object other) {
            if (!(other instanceof State)) {
                return false;
            }
            State that = (State) other;
            return perm.equals(that.perm) && count.equals(that.count);
        }

        @Override
        public int hashCode() {
            return Objects.hash(perm, count);
        }
    }
}