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

public class Euler1010 {
    private static final long MOD = 1_234_567_891L;
    private static final long PERIOD = MOD - 1;

    private static long power(long base, long exponent) {
        long result = 1;
        while (exponent != 0) {
            if ((exponent & 1) != 0) result = result * base % MOD;
            base = base * base % MOD;
            exponent >>= 1;
        }
        return result;
    }

    private static long add(long a, long b) {
        long sum = a + b;
        return sum >= PERIOD ? sum - PERIOD : sum;
    }

    private static final class Counts {
        long partitions;
        final long[] hooks;

        Counts(long partitions, long[] hooks) {
            this.partitions = partitions;
            this.hooks = hooks;
        }
    }

    private static Counts countHooks(int m, int n) {
        if (m < 1 || n < 0) throw new IllegalArgumentException("Invalid penguin or step count");
        if (n == 0) return new Counts(1, new long[1]);
        m = Math.min(m, n);
        int baseline = m * (m - 1) / 2;
        int degree = n + baseline;
        long[] partitions = new long[degree + 1];
        long[] quotient = new long[degree + 1];
        Counts result = new Counts(0, new long[n + 1]);
        partitions[0] = 1;

        for (int r = 0; r < m; ++r) {
            int j = m - r;
            int shift = baseline - r * (r - 1) / 2;
            for (int s = 0; s <= n + shift; ++s) {
                quotient[s] = add(partitions[s], s >= j ? quotient[s - j] : 0);
            }

            // Extract the aggregate hook counts from P_r(q)/(1-q^j).
            for (int h = 1; h <= n; ++h) {
                long contribution = 0;
                for (int t = 1, s = n + shift - h; t <= j && s >= 0; ++t, s -= h) {
                    contribution += quotient[s];
                }
                contribution %= PERIOD;
                result.hooks[h] = add(result.hooks[h],
                        j % 2 != 0 ? contribution : (PERIOD - contribution) % PERIOD);
            }

            int part = r + 1;
            for (int s = part; s <= degree; ++s) {
                partitions[s] = add(partitions[s], partitions[s - part]);
            }
        }
        result.partitions = partitions[n];
        return result;
    }

    private static long productFromHooks(Counts counts) {
        long factorial = 1;
        long denominator = 1;
        for (int h = 1; h < counts.hooks.length; ++h) {
            factorial = factorial * h % MOD;
            denominator = denominator * power(h, counts.hooks[h]) % MOD;
        }
        return power(factorial, counts.partitions) * power(denominator, MOD - 2) % MOD;
    }

    private static long solve(int m, int n) {
        return productFromHooks(countHooks(m, n));
    }

    private static void require(boolean condition, String description) {
        if (!condition) throw new IllegalStateException("Check failed: " + description);
    }

    private static void checkWalks(int m, int maxSteps) {
        List<Integer> initial = new ArrayList<>();
        for (int i = 1; i <= m; ++i) initial.add(i);
        Map<List<Integer>, Long> states = new HashMap<>();
        states.put(initial, 1L);
        for (int n = 0; n <= maxSteps; ++n) {
            long expected = 1;
            long[] hooks = new long[n + 1];
            for (Map.Entry<List<Integer>, Long> entry : states.entrySet()) {
                List<Integer> positions = entry.getKey();
                expected = expected * (entry.getValue() % MOD) % MOD;
                int[] shape = new int[m];
                for (int i = 0; i < m; ++i) shape[i] = positions.get(m - 1 - i) - (m - i);
                for (int row = 0; row < m; ++row) {
                    for (int col = 0; col < shape[row]; ++col) {
                        int hook = shape[row] - col;
                        for (int below = row + 1; below < m; ++below) {
                            if (shape[below] > col) ++hook;
                        }
                        ++hooks[hook];
                    }
                }
            }
            Counts actual = countHooks(m, n);
            String label = "m=" + m + ", n=" + n;
            require(actual.partitions == states.size(), "endpoint count for " + label);
            require(Arrays.equals(actual.hooks, hooks), "hook counts for " + label);
            require(productFromHooks(actual) == expected, "legal-walk product for " + label);
            if (n == maxSteps) break;
            Map<List<Integer>, Long> next = new HashMap<>();
            for (Map.Entry<List<Integer>, Long> entry : states.entrySet()) {
                List<Integer> positions = entry.getKey();
                for (int i = 0; i < m; ++i) {
                    if (i + 1 < m && positions.get(i) + 1 == positions.get(i + 1)) continue;
                    List<Integer> moved = new ArrayList<>(positions);
                    moved.set(i, moved.get(i) + 1);
                    next.put(moved, next.getOrDefault(moved, 0L) + entry.getValue());
                }
            }
            states = next;
        }
    }

    private static void runTests() {
        require(solve(2, 4) == 6, "F(2,4)");
        require(solve(3, 6) == 180_000, "F(3,6)");
        require(solve(5, 10) == 411_456_133, "F(5,10)");
        for (int m = 1; m <= 16; ++m) checkWalks(m, 16);
        Counts target = countHooks(150, 300);
        long total = 0;
        for (long count : target.hooks) total = add(total, count);
        require(total == 300 * target.partitions % PERIOD, "total target hook count");
        require(productFromHooks(target) == 892_087_998, "F(150,300)");
        System.out.println("All checks passed.");
    }

    public static void main(String[] args) {
        try {
            if (args.length == 1 && args[0].equals("--self-test")) {
                runTests();
            } else if (args.length == 0) {
                System.out.println(solve(150, 300));
            } else {
                throw new IllegalArgumentException("Usage: Euler1010 [--self-test]");
            }
        } catch (IllegalArgumentException | IllegalStateException error) {
            System.err.println(error.getMessage());
            System.exit(1);
        }
    }
}