Fibonacci numbers follow a simple rule: each new number is the sum of the two before it. Given n, return the n-th Fibonacci number, where fib(0) = 0, fib(1) = 1, and fib(n) = fib(n-1) + fib(n-2). Try not to recompute the same values again and again.

def fib(n: int) -> int: