





import timeit



class 				_UpperCamelCase       :

       def __init__(		self:			Any       , _SCREAMING_SNAKE_CASE:			List[Any]		)							->			Optional[Any]:




              """simple docstring"""


              if isinstance(_SCREAMING_SNAKE_CASE       , _SCREAMING_SNAKE_CASE		):  # Initializes a matrix identical to the one provided.
                     UpperCamelCase_ 							=	arg
                     UpperCamelCase_ 							=	len(_SCREAMING_SNAKE_CASE		)
              else:  # Initializes a square matrix of the given size and set values to zero.
                     UpperCamelCase_ 							=	arg
                     UpperCamelCase_ 							=	[[0 for _ in range(self.n		)] for _ in range(self.n		)]



       def __mul__(		self:			Union[str, Any]       , _SCREAMING_SNAKE_CASE:			List[str]		)							->			Dict:




              """simple docstring"""


              UpperCamelCase_ 							=	Matrix(self.n		)
              for i in range(self.n		):
                     for j in range(self.n		):
                            for k in range(self.n		):
                                   matrix.t[i][j] += self.t[i][k] * b.t[k][j]
              return matrix




def 			lowerCAmelCase_			(				UpperCamelCase_       ,		UpperCamelCase_	)  ->		Optional[Any]:
       UpperCamelCase_ 							=	Matrix([[1, 0], [0, 1]]	)
       while b > 0:
              if b & 1:
                     matrix *= a
              a *= a
              b >>= 1
       return matrix




def 			lowerCAmelCase_			(				UpperCamelCase_       ,		UpperCamelCase_       ,		UpperCamelCase_	)  ->		Union[str, Any]:
       # Trivial Cases
       if n == 1:
              return fa
       elif n == 2:
              return fa
       UpperCamelCase_ 							=	Matrix([[1, 1], [1, 0]]	)
       UpperCamelCase_ 							=	modular_exponentiation(UpperCamelCase_       ,		n - 2	)
       return fa * matrix.t[0][0] + fa * matrix.t[0][1]




def 			lowerCAmelCase_			(				UpperCamelCase_       ,		UpperCamelCase_       ,		UpperCamelCase_	)  ->		List[Any]:
       # Trivial Cases
       if n == 1:
              return fa
       elif n == 2:
              return fa

       UpperCamelCase_ 							=	fa
       UpperCamelCase_ 							=	fa
       n -= 2

       while n > 0:
              UpperCamelCase_							,			UpperCamelCase_ 							=	fn_a + fn_a, fn_a
              n -= 1

       return fn_a




def 			lowerCAmelCase_			(				)  ->		Optional[int]:
       UpperCamelCase_ 							=	"\nfrom random import randint\nfrom __main__ import fibonacci_with_matrix_exponentiation\n"
       UpperCamelCase_ 							=	"fibonacci_with_matrix_exponentiation(randint(1,70000), 1, 1)"
       UpperCamelCase_ 							=	timeit.timeit(setup=UpperCamelCase_       ,		stmt=UpperCamelCase_       ,		number=100	)
       print("With matrix exponentiation the average execution time is "       ,		exec_time / 100	)
       return exec_time




def 			lowerCAmelCase_			(				)  ->		Tuple:
       UpperCamelCase_ 							=	"\nfrom random import randint\nfrom __main__ import simple_fibonacci\n"
       UpperCamelCase_ 							=	"simple_fibonacci(randint(1,70000), 1, 1)"
       UpperCamelCase_ 							=	timeit.timeit(setup=UpperCamelCase_       ,		stmt=UpperCamelCase_       ,		number=100	)
       print(
           "Without matrix exponentiation the average execution time is "       ,		exec_time / 100	)
       return exec_time




def 			lowerCAmelCase_			(				)  ->		List[Any]:
       matrix_exponentiation_time()
       simple_fibonacci_time()


if __name__ == "__main__":
     main()





def 				UpperCamelCase_	(					__snake_case      :    set						,      __snake_case      :    set  )->   set:




						'''simple docstring'''
						assert isinstance(__snake_case						,      __snake_case  ), F'''The input value of [set_a={set_a}] is not a set'''
						assert isinstance(__snake_case						,      __snake_case  ), F'''The input value of [set_b={set_b}] is not a set'''

						return {a + b for a in set_a for b in set_b}


if __name__ == "__main__":
					from doctest import testmod

					testmod()

