




'''simple docstring'''


import functools
from math import sqrt
from time import time



def    _SCREAMING_SNAKE_CASE    (			UpperCamelCase__						:				str   ,						*UpperCamelCase__						:				List[Any]   ,						**UpperCamelCase__						:				int							):




     """simple docstring"""


     a_    :       Optional[int]    	=     time()
     a_    :       str    	=     func(*UpperCamelCase__   ,						**UpperCamelCase__							)
     a_    :       Optional[Any]    	=     time()
     if int(end - start							) > 0:
          print(F"{func.__name__} runtime: {(end - start):0.4f} s"							)
     else:
          print(F"{func.__name__} runtime: {(end - start) * 1000:0.4f} ms"							)
     return output



def    _SCREAMING_SNAKE_CASE    (			UpperCamelCase__						:				int							):




     """simple docstring"""


     if n < 0:
          raise Exception("""n is negative"""							)
     if n == 0:
          return [0]
     a_    :       Optional[Any]    	=     [0, 1]
     for _ in range(n - 1							):
          fib.append(fib[-1] + fib[-2]							)
     return fib



def    _SCREAMING_SNAKE_CASE    (			UpperCamelCase__						:				int							):




     """simple docstring"""


     def fib_recursive_term(UpperCamelCase__						:				int							) -> int:
          if i < 0:
               raise Exception("""n is negative"""							)
          if i < 2:
               return i
          return fib_recursive_term(i - 1							) + fib_recursive_term(i - 2							)

     if n < 0:
          raise Exception("""n is negative"""							)
     return [fib_recursive_term(UpperCamelCase__							) for i in range(n + 1							)]



def    _SCREAMING_SNAKE_CASE    (			UpperCamelCase__						:				int							):




     """simple docstring"""


     @functools.cache
     def fib_recursive_term(UpperCamelCase__						:				int							) -> int:
          if i < 0:
               raise Exception("""n is negative"""							)
          if i < 2:
               return i
          return fib_recursive_term(i - 1							) + fib_recursive_term(i - 2							)

     if n < 0:
          raise Exception("""n is negative"""							)
     return [fib_recursive_term(UpperCamelCase__							) for i in range(n + 1							)]



def    _SCREAMING_SNAKE_CASE    (			UpperCamelCase__						:				int							):




     """simple docstring"""


     if n < 0:
          raise Exception("""n is negative"""							)
     # Cache must be outside recursuive function
     # other it will reset every time it calls itself.
     a_    :       dict[int, int]    	=     {0: 0, 1: 1, 2: 1}  # Prefilled cache

     def rec_fn_memoized(UpperCamelCase__						:				int							) -> int:
          if num in cache:
               return cache[num]

          a_    :       Optional[Any]    	=     rec_fn_memoized(num - 1							) + rec_fn_memoized(num - 2							)
          a_    :       List[Any]    	=     value
          return value

     return [rec_fn_memoized(UpperCamelCase__							) for i in range(n + 1							)]



def    _SCREAMING_SNAKE_CASE    (			UpperCamelCase__						:				int							):




     """simple docstring"""


     if n < 0:
          raise Exception("""n is negative"""							)
     if n >= 1475:
          raise Exception("""n is too large"""							)
     a_    :       int    	=     sqrt(5							)
     a_    :       str    	=     (1 + sqrt_a) / 2
     return [round(phi**i / sqrt_a							) for i in range(n + 1							)]


if __name__ == "__main__":
 lowerCAmelCase_			:     int							    =     30
 time_func(fib_iterative, num)
 time_func(fib_recursive, num)  # Around 3s runtime
 time_func(fib_recursive_cached, num)  # Around 0ms runtime
 time_func(fib_memoization, num)
 time_func(fib_binet, num)






'''simple docstring'''


def    _SCREAMING_SNAKE_CASE    (			UpperCamelCase__						:				int = 1000							):




     """simple docstring"""


     return sum(i for i in range(UpperCamelCase__							) if i % 3 == 0 or i % 5 == 0							)


if __name__ == "__main__":
 print(f"{solution() = }")
