




import functools
from math import sqrt
from time import time



def 	UpperCAmelCase_    (	__UpperCamelCase,				*__UpperCamelCase,				**__UpperCamelCase	):
    SCREAMING_SNAKE_CASE__								=time()
    SCREAMING_SNAKE_CASE__								=func(*__UpperCamelCase,				**__UpperCamelCase	)
    SCREAMING_SNAKE_CASE__								=time()
    if int(end - start	) > 0:
        print(f"""{func.__name__} runtime: {(end - start):0.4f} s"""	)
    else:
        print(f"""{func.__name__} runtime: {(end - start) * 1_000:0.4f} ms"""	)
    return output



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



def 	UpperCAmelCase_    (	__UpperCamelCase	):

    def fib_recursive_term(__UpperCamelCase	) -> 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 	UpperCAmelCase_    (	__UpperCamelCase	):

    @functools.cache
    def fib_recursive_term(__UpperCamelCase	) -> 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 	UpperCAmelCase_    (	__UpperCamelCase	):
    if n < 0:
        raise Exception("""n is negative"""	)
    # Cache must be outside recursuive function
    # other it will reset every time it calls itself.
    SCREAMING_SNAKE_CASE__								={0: 0, 1: 1, 2: 1}  # Prefilled cache

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

        SCREAMING_SNAKE_CASE__								=rec_fn_memoized(num - 1	) + rec_fn_memoized(num - 2	)
        SCREAMING_SNAKE_CASE__								=value
        return value

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



def 	UpperCAmelCase_    (	__UpperCamelCase	):
    if n < 0:
        raise Exception("""n is negative"""	)
    if n >= 1_475:
        raise Exception("""n is too large"""	)
    SCREAMING_SNAKE_CASE__								=sqrt(5	)
    SCREAMING_SNAKE_CASE__								=(1 + sqrt_a) / 2
    return [round(phi**i / sqrt_a	) for i in range(n + 1	)]


if __name__ == "__main__":
    lowerCamelCase_  						=   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)












import unittest
from dataclasses import dataclass
from typing import Optional

from transformers.utils import ModelOutput
@dataclass
class       __a					( __lowerCamelCase     ):


     """simple docstring"""


     _A				:    float
     _A				:    Optional[float]									=  None
     _A				:    Optional[float]									=  None






class       __a					( unittest.TestCase     ):


     """simple docstring"""


     def   __A				(	self			: Dict						)		->   Optional[int]:


         '''simple docstring'''





         SCREAMING_SNAKE_CASE__								=ModelOutputTest(a=3_0						)
         self.assertEqual(x.a				,3_0						)
         self.assertIsNone(x.b						)
         self.assertIsNone(x.c						)
         with self.assertRaises(_UpperCamelCase						):
             SCREAMING_SNAKE_CASE__								=x.d




     def   __A				(	self			: Tuple						)		->   Dict:


         '''simple docstring'''





         SCREAMING_SNAKE_CASE__								=ModelOutputTest(a=3_0				,b=1_0						)
         self.assertEqual(x[0]				,3_0						)
         self.assertEqual(x[1]				,1_0						)
         self.assertEqual(x[:2]				,(3_0, 1_0)						)
         self.assertEqual(x[:]				,(3_0, 1_0)						)

         SCREAMING_SNAKE_CASE__								=ModelOutputTest(a=3_0				,c=1_0						)
         self.assertEqual(x[0]				,3_0						)
         self.assertEqual(x[1]				,1_0						)
         self.assertEqual(x[:2]				,(3_0, 1_0)						)
         self.assertEqual(x[:]				,(3_0, 1_0)						)




     def   __A				(	self			: List[str]						)		->   Dict:


         '''simple docstring'''





         SCREAMING_SNAKE_CASE__								=ModelOutputTest(a=3_0				,b=1_0						)
         self.assertEqual(x["""a"""]				,3_0						)
         self.assertEqual(x["""b"""]				,1_0						)
         with self.assertRaises(_UpperCamelCase						):
             SCREAMING_SNAKE_CASE__								=x["""c"""]

         SCREAMING_SNAKE_CASE__								=ModelOutputTest(a=3_0				,c=1_0						)
         self.assertEqual(x["""a"""]				,3_0						)
         self.assertEqual(x["""c"""]				,1_0						)
         with self.assertRaises(_UpperCamelCase						):
             SCREAMING_SNAKE_CASE__								=x["""b"""]




     def   __A				(	self			: Optional[int]						)		->   List[str]:


         '''simple docstring'''





         SCREAMING_SNAKE_CASE__								=ModelOutputTest(a=3_0						)
         self.assertEqual(list(x.keys()						)				,["""a"""]						)
         self.assertEqual(list(x.values()						)				,[3_0]						)
         self.assertEqual(list(x.items()						)				,[("""a""", 3_0)]						)
         self.assertEqual(list(_UpperCamelCase						)				,["""a"""]						)

         SCREAMING_SNAKE_CASE__								=ModelOutputTest(a=3_0				,b=1_0						)
         self.assertEqual(list(x.keys()						)				,["""a""", """b"""]						)
         self.assertEqual(list(x.values()						)				,[3_0, 1_0]						)
         self.assertEqual(list(x.items()						)				,[("""a""", 3_0), ("""b""", 1_0)]						)
         self.assertEqual(list(_UpperCamelCase						)				,["""a""", """b"""]						)

         SCREAMING_SNAKE_CASE__								=ModelOutputTest(a=3_0				,c=1_0						)
         self.assertEqual(list(x.keys()						)				,["""a""", """c"""]						)
         self.assertEqual(list(x.values()						)				,[3_0, 1_0]						)
         self.assertEqual(list(x.items()						)				,[("""a""", 3_0), ("""c""", 1_0)]						)
         self.assertEqual(list(_UpperCamelCase						)				,["""a""", """c"""]						)

         with self.assertRaises(_UpperCamelCase						):
             SCREAMING_SNAKE_CASE__								=x.update({"""d""": 2_0}						)
         with self.assertRaises(_UpperCamelCase						):
             del x["a"]
         with self.assertRaises(_UpperCamelCase						):
             SCREAMING_SNAKE_CASE__								=x.pop("""a"""						)
         with self.assertRaises(_UpperCamelCase						):
             SCREAMING_SNAKE_CASE__								=x.setdefault("""d"""				,3_2						)




     def   __A				(	self			: int						)		->   List[Any]:


         '''simple docstring'''





         SCREAMING_SNAKE_CASE__								=ModelOutputTest(a=3_0						)
         SCREAMING_SNAKE_CASE__								=1_0
         self.assertEqual(x.a				,1_0						)
         self.assertEqual(x["""a"""]				,1_0						)




     def   __A				(	self			: Union[str, Any]						)		->   Optional[Any]:


         '''simple docstring'''





         SCREAMING_SNAKE_CASE__								=ModelOutputTest(a=3_0						)
         SCREAMING_SNAKE_CASE__								=1_0
         self.assertEqual(x.a				,1_0						)
         self.assertEqual(x["""a"""]				,1_0						)




     def   __A				(	self			: Dict						)		->   List[str]:


         '''simple docstring'''





         SCREAMING_SNAKE_CASE__								=ModelOutputTest({"""a""": 3_0, """b""": 1_0}						)
         self.assertEqual(list(x.keys()						)				,["""a""", """b"""]						)
         self.assertEqual(x.a				,3_0						)
         self.assertEqual(x.b				,1_0						)




     def   __A				(	self			: Optional[int]						)		->   int:


         '''simple docstring'''





         SCREAMING_SNAKE_CASE__								=ModelOutputTest([("""a""", 3_0), ("""b""", 1_0)]						)
         self.assertEqual(list(x.keys()						)				,["""a""", """b"""]						)
         self.assertEqual(x.a				,3_0						)
         self.assertEqual(x.b				,1_0						)

         with self.assertRaises(_UpperCamelCase						):
             SCREAMING_SNAKE_CASE__								=ModelOutputTest([("""a""", 3_0), (1_0, 1_0)]						)

         SCREAMING_SNAKE_CASE__								=ModelOutputTest(a=(3_0, 3_0)						)
         self.assertEqual(list(x.keys()						)				,["""a"""]						)
         self.assertEqual(x.a				,(3_0, 3_0)						)






