#!/usr/bin/env python3
"""Project Euler Problem 1005 - Median Prime List."""

from __future__ import annotations

import argparse
from dataclasses import dataclass

DEFAULT_TARGET = 2026
MOD = 1_000_000_000


@dataclass
class PrimeDp:
    target: int
    primes: list[int]
    suffix_count: list[list[int]]


def primes_up_to(limit: int) -> list[int]:
    if limit < 2:
        return []

    composite = [False] * (limit + 1)
    p = 2
    while p * p <= limit:
        if not composite[p]:
            for multiple in range(p * p, limit + 1, p):
                composite[multiple] = True
        p += 1

    return [value for value in range(2, limit + 1) if not composite[value]]


def build_dp(target: int) -> PrimeDp:
    primes = primes_up_to(target)
    count = len(primes)
    suffix_count = [[0] * (target + 1) for _ in range(count + 1)]
    suffix_count[count][0] = 1

    for i in range(count - 1, -1, -1):
        prime = primes[i]
        next_row = suffix_count[i + 1]
        row = suffix_count[i]
        for total in range(target + 1):
            ways = next_row[total]
            if total >= prime:
                ways += next_row[total - prime]
            row[total] = ways

    return PrimeDp(target=target, primes=primes, suffix_count=suffix_count)


def kth_prime_list(dp: PrimeDp, rank: int) -> list[int]:
    total = dp.suffix_count[0][dp.target]
    if rank <= 0 or rank > total:
        raise ValueError("requested rank is outside the available prime lists")

    remaining = dp.target
    start = 0
    result: list[int] = []

    while remaining > 0:
        found = False
        for i in range(start, len(dp.primes)):
            prime = dp.primes[i]
            if prime > remaining:
                break

            block = dp.suffix_count[i + 1][remaining - prime]
            if rank > block:
                rank -= block
                continue

            result.append(prime)
            remaining -= prime
            start = i + 1
            found = True
            break

        if not found:
            raise RuntimeError("could not unrank the requested prime list")

    return result


def median_prime_list(dp: PrimeDp) -> list[int]:
    total = dp.suffix_count[0][dp.target]
    if total == 0:
        raise ValueError("there is no prime list for the requested target")
    return kth_prime_list(dp, (total + 1) // 2)


def product_mod(values: list[int]) -> int:
    product = 1
    for value in values:
        product = product * value % MOD
    return product


def enumerate_bruteforce(
    primes: list[int],
    start: int,
    remaining: int,
    current: list[int],
    lists: list[list[int]],
) -> None:
    if remaining == 0:
        lists.append(current.copy())
        return

    for i in range(start, len(primes)):
        prime = primes[i]
        if prime > remaining:
            break
        current.append(prime)
        enumerate_bruteforce(primes, i + 1, remaining - prime, current, lists)
        current.pop()


def brute_lists(target: int) -> list[list[int]]:
    lists: list[list[int]] = []
    enumerate_bruteforce(primes_up_to(target), 0, target, [], lists)
    return lists


def run_checkpoints() -> None:
    dp20 = build_dp(20)
    expected = [[2, 5, 13], [2, 7, 11], [3, 17], [7, 13]]
    assert brute_lists(20) == expected
    assert dp20.suffix_count[0][20] == 4
    assert median_prime_list(dp20) == [2, 7, 11]
    assert product_mod(median_prime_list(dp20)) == 154

    for target in range(2, 61):
        dp = build_dp(target)
        lists = brute_lists(target)
        assert dp.suffix_count[0][target] == len(lists)

        if lists:
            assert median_prime_list(dp) == lists[(len(lists) - 1) // 2]
            assert kth_prime_list(dp, 1) == lists[0]
            assert kth_prime_list(dp, (len(lists) + 1) // 2) == lists[(len(lists) - 1) // 2]
            assert kth_prime_list(dp, len(lists)) == lists[-1]


def parse_args() -> argparse.Namespace:
    parser = argparse.ArgumentParser(description="Solve Project Euler Problem 1005.")
    parser.add_argument("target", nargs="?", type=int, default=DEFAULT_TARGET)
    parser.add_argument("--skip-checkpoints", action="store_true")
    return parser.parse_args()


def main() -> None:
    args = parse_args()
    if args.target < 0:
        raise SystemExit("target must be nonnegative")

    if not args.skip_checkpoints:
        run_checkpoints()

    dp = build_dp(args.target)
    print(f"{product_mod(median_prime_list(dp)):09d}")


if __name__ == "__main__":
    main()