you should include a faster version of the fibonacci function with exponentiation by squaring

  def fibonacci(k):
    a,b=(0,1)
    for i in range(k.bit_length()-1,-1,-1):
      d=a**2
      c=2*a*b-d
      d+=b**2
      (a,b)=(d,c+d) if k>>i&1 else (c,d)
    return a

you can also encode polynomials into integers; see https://mathstodon.xyz/@peterluschny/116320199782572958 and the following prog from https://codegolf.stackexchange.com/a/279771

  lambda n:pow(p:=2<<n,n,p*p+~p)//p

also you could at least wrap the existing one in a `functools.cache`