Memoised Fibonacci

The plain recursive Fibonacci function calls itself twice per step, so fib(30) makes over a million calls and fib(90) would never finish, because the same values are recomputed again and again. Write fib(n: int, memo: dict[int, int]) -> int that fixes this with a memo: the dict maps an n that has already been solved to its answer. First test n in memo (the in test on a dict) and return the stored memo[n] if it is there; then keep the base case, returning n itself when n is below 2; otherwise add the two recursive calls, each passing the same memo along, store that result in memo[n] and return it. The sequence starts 0, 1, 1, 2, 3, 5, 8. Do NOT write a main block or any top-level test code; the tests construct the calls with an empty dict. Input: one integer n, no prompt, which the tests read and pass to your function before printing the value it returns.