#!/usr/bin/env python3
"""Project Euler Problem 1004 - Balanced Integer."""

from __future__ import annotations

MOD = 1_000_000_007
DIGITS = 10
MAX_CELLS = DIGITS * DIGITS

factorial = [1] * (MAX_CELLS + 1)
for i in range(1, MAX_CELLS + 1):
    factorial[i] = factorial[i - 1] * i % MOD


def mod_inverse(value: int) -> int:
    return pow(value, MOD - 2, MOD)


def shape_word_count(partition: list[int]) -> int:
    cells = sum(partition)
    hook_product = 1
    content_product = 1

    for i, row_len in enumerate(partition):
        for j in range(row_len):
            below = sum(1 for later_row in partition[i + 1 :] if later_row > j)
            right = row_len - j - 1
            hook = right + below + 1
            content = DIGITS + (j + 1) - (i + 1)
            hook_product = hook_product * hook % MOD
            content_product = content_product * content % MOD

    inv_hooks = mod_inverse(hook_product)
    return factorial[cells] * content_product % MOD * inv_hooks % MOD * inv_hooks % MOD


def enumerate_partitions(
    max_part: int,
    max_rows: int,
    partition: list[int],
    max_cells: int,
) -> tuple[int, int]:
    balanced = 0
    decreasing_excess = 0

    if partition:
        cells = sum(partition)
        if cells <= max_cells:
            ways = shape_word_count(partition)
            width = partition[0]
            height = len(partition)
            if width == height:
                balanced = (balanced + ways) % MOD
            if height == width + 1:
                decreasing_excess = (decreasing_excess + ways) % MOD

    if len(partition) == max_rows:
        return balanced, decreasing_excess

    used = sum(partition)
    for next_part in range(max_part, 0, -1):
        if used + next_part > max_cells:
            continue
        partition.append(next_part)
        sub_balanced, sub_excess = enumerate_partitions(
            next_part, max_rows, partition, max_cells
        )
        balanced = (balanced + sub_balanced) % MOD
        decreasing_excess = (decreasing_excess + sub_excess) % MOD
        partition.pop()

    return balanced, decreasing_excess


def count_all_words(max_cells: int) -> tuple[int, int]:
    return enumerate_partitions(DIGITS, DIGITS, [], max_cells)


def positive_balanced_count(max_digits: int) -> int:
    balanced, _ = count_all_words(max_digits)
    _, decreasing_excess = count_all_words(max_digits - 1)
    return (balanced - decreasing_excess - 1) % MOD


def run_checkpoints() -> None:
    assert positive_balanced_count(4) == 2274


def main() -> None:
    run_checkpoints()
    print(positive_balanced_count(MAX_CELLS))


if __name__ == "__main__":
    main()