"""A correct implementation that meets the contract.

Deliberately built on a *different* algorithm from the oracle: this uses the
Akiyama-Tanigawa transform, while ``reference_bernoulli`` uses the binomial
recurrence.  Two independent routes to the same exact values is much stronger
evidence than one routine agreeing with a copy of itself.

Note the one-line convention adjustment.  Akiyama-Tanigawa naturally produces the
*second* Bernoulli numbers with ``B1 = +1/2``; this course fixes the first
convention, so ``B1`` is negated.  Writing that down is the difference between an
implementation you can defend and one that happens to pass.
"""

from fractions import Fraction


def bernoulli(n: int) -> Fraction:
    """Return B_n exactly, using the first-Bernoulli convention (B1 = -1/2)."""
    if n < 0:
        raise ValueError("n must be >= 0")

    row = [Fraction(0)] * (n + 1)
    for m in range(n + 1):
        row[m] = Fraction(1, m + 1)
        for j in range(m, 0, -1):
            row[j - 1] = j * (row[j - 1] - row[j])

    value = row[0]
    # Akiyama-Tanigawa yields B1 = +1/2; this course uses B1 = -1/2.
    if n == 1:
        return -value
    return value