import sys

MOD = 1_234_567_891
PERIOD = MOD - 1


def count_hooks(m, n):
    if m < 1 or n < 0:
        raise ValueError("Invalid penguin or step count")
    if n == 0:
        return 1, [0]
    m = min(m, n)
    baseline = m * (m - 1) // 2
    degree = n + baseline
    partitions = [0] * (degree + 1)
    quotient = [0] * (degree + 1)
    hooks = [0] * (n + 1)
    partitions[0] = 1

    for r in range(m):
        j = m - r
        shift = baseline - r * (r - 1) // 2
        limit = n + shift
        for s in range(limit + 1):
            quotient[s] = (partitions[s] + (quotient[s - j] if s >= j else 0)) % PERIOD

        # Extract the aggregate hook counts from P_r(q)/(1-q^j).
        for h in range(1, n + 1):
            contribution = 0
            s = limit - h
            for _ in range(j):
                if s < 0:
                    break
                contribution += quotient[s]
                s -= h
            if j % 2 == 0:
                contribution = -contribution
            hooks[h] = (hooks[h] + contribution) % PERIOD

        part = r + 1
        for s in range(part, degree + 1):
            partitions[s] = (partitions[s] + partitions[s - part]) % PERIOD
    return partitions[n], hooks


def product_from_hooks(partitions, hooks):
    factorial = 1
    denominator = 1
    for h in range(1, len(hooks)):
        factorial = factorial * h % MOD
        denominator = denominator * pow(h, hooks[h], MOD) % MOD
    return pow(factorial, partitions, MOD) * pow(denominator, MOD - 2, MOD) % MOD


def solve(m, n):
    return product_from_hooks(*count_hooks(m, n))


def require(condition, description):
    if not condition:
        raise AssertionError("Check failed: " + description)


def check_walks(m, max_steps):
    states = {tuple(range(1, m + 1)): 1}
    for n in range(max_steps + 1):
        expected = 1
        hooks = [0] * (n + 1)
        for positions, ways in states.items():
            expected = expected * ways % MOD
            shape = [positions[m - 1 - i] - (m - i) for i in range(m)]
            for row in range(m):
                for col in range(shape[row]):
                    hook = shape[row] - col
                    hook += sum(shape[below] > col for below in range(row + 1, m))
                    hooks[hook] += 1
        actual = count_hooks(m, n)
        label = f"m={m}, n={n}"
        require(actual[0] == len(states), "endpoint count for " + label)
        require(actual[1] == hooks, "hook counts for " + label)
        require(product_from_hooks(*actual) == expected, "legal-walk product for " + label)
        if n == max_steps:
            break
        following = {}
        for positions, ways in states.items():
            for i in range(m):
                if i + 1 < m and positions[i] + 1 == positions[i + 1]:
                    continue
                moved = list(positions)
                moved[i] += 1
                moved = tuple(moved)
                following[moved] = following.get(moved, 0) + ways
        states = following


def run_tests():
    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 m in range(1, 17):
        check_walks(m, 16)
    partitions, hooks = count_hooks(150, 300)
    require(sum(hooks) % PERIOD == 300 * partitions % PERIOD, "total target hook count")
    require(product_from_hooks(partitions, hooks) == 892_087_998, "F(150,300)")
    print("All checks passed.")


def main():
    if sys.argv[1:] == ["--self-test"]:
        run_tests()
    elif len(sys.argv) == 1:
        print(solve(150, 300))
    else:
        raise ValueError("Usage: Euler1010.py [--self-test]")


if __name__ == "__main__":
    try:
        main()
    except (ValueError, AssertionError) as error:
        print(error, file=sys.stderr)
        sys.exit(1)