def _fib(n: int) -> tuple[int, int]:
    if n == 0:  # (F(0), F(1))
        return (0, 1)

    # F(2n) = F(n)[2F(n+1) − F(n)]
    # F(2n+1) = F(n+1)^2+F(n)^2
    a, b = _fib(n // 2)
    c = a * (b * 2 - a)
    d = a * a + b * b
    return (d, c + d) if n % 2 else (c, d)