




import timeit




class       UpperCAmelCase_   :




							'''simple docstring'''



							def __init__(       self							:						str							,  a							:						Optional[Any]      )      ->       Optional[int]:
										if isinstance(a							,  a      ):  # Initializes a matrix identical to the one provided.
													SCREAMING_SNAKE_CASE     =       arg
													SCREAMING_SNAKE_CASE     =       len(a      )
										else:  # Initializes a square matrix of the given size and set values to zero.
													SCREAMING_SNAKE_CASE     =       arg
													SCREAMING_SNAKE_CASE     =       [[0 for _ in range(self.n      )] for _ in range(self.n      )]







							def __mul__(       self							:						List[Any]							,  a							:						Union[str, Any]      )      ->       Dict:
										SCREAMING_SNAKE_CASE     =       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_     (     SCREAMING_SNAKE_CASE       ,						SCREAMING_SNAKE_CASE ):
			'''simple docstring'''
			SCREAMING_SNAKE_CASE     =       Matrix([[1, 0], [0, 1]] )
			while b > 0:
						if b & 1:
									matrix *= a
						a *= a
						b >>= 1
			return matrix
def        lowerCamelCase_     (     SCREAMING_SNAKE_CASE       ,						SCREAMING_SNAKE_CASE       ,						SCREAMING_SNAKE_CASE ):
			'''simple docstring'''
			# Trivial Cases
			if n == 1:
						return fa
			elif n == 2:
						return fa
			SCREAMING_SNAKE_CASE     =       Matrix([[1, 1], [1, 0]] )
			SCREAMING_SNAKE_CASE     =       modular_exponentiation(SCREAMING_SNAKE_CASE       ,						n - 2 )
			return fa * matrix.t[0][0] + fa * matrix.t[0][1]
def        lowerCamelCase_     (     SCREAMING_SNAKE_CASE       ,						SCREAMING_SNAKE_CASE       ,						SCREAMING_SNAKE_CASE ):
			'''simple docstring'''
			# Trivial Cases
			if n == 1:
						return fa
			elif n == 2:
						return fa

			SCREAMING_SNAKE_CASE     =       fa
			SCREAMING_SNAKE_CASE     =       fa
			n -= 2

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

			return fn_a
def        lowerCamelCase_     (     ):
			'''simple docstring'''
			SCREAMING_SNAKE_CASE     =       """
from random import randint
from __main__ import fibonacci_with_matrix_exponentiation
"""
			SCREAMING_SNAKE_CASE     =       """fibonacci_with_matrix_exponentiation(randint(1,70000), 1, 1)"""
			SCREAMING_SNAKE_CASE     =       timeit.timeit(setup=SCREAMING_SNAKE_CASE       ,						stmt=SCREAMING_SNAKE_CASE       ,						number=1_00 )
			print("""With matrix exponentiation the average execution time is """       ,						exec_time / 1_00 )
			return exec_time
def        lowerCamelCase_     (     ):
			'''simple docstring'''
			SCREAMING_SNAKE_CASE     =       """
from random import randint
from __main__ import simple_fibonacci
"""
			SCREAMING_SNAKE_CASE     =       """simple_fibonacci(randint(1,70000), 1, 1)"""
			SCREAMING_SNAKE_CASE     =       timeit.timeit(setup=SCREAMING_SNAKE_CASE       ,						stmt=SCREAMING_SNAKE_CASE       ,						number=1_00 )
			print(
			    """Without matrix exponentiation the average execution time is """       ,						exec_time / 1_00 )
			return exec_time
def        lowerCamelCase_     (     ):
			'''simple docstring'''
			matrix_exponentiation_time()
			simple_fibonacci_time()


if __name__ == "__main__":
		main()












def        lowerCamelCase_     (     SCREAMING_SNAKE_CASE       ,						SCREAMING_SNAKE_CASE ):
			'''simple docstring'''
			if n == 0:
						return 1

			elif n % 2 == 1:
						return binary_exponentiation(SCREAMING_SNAKE_CASE       ,						n - 1 ) * a

			else:
						SCREAMING_SNAKE_CASE     =       binary_exponentiation(SCREAMING_SNAKE_CASE       ,						n / 2 )
						return b * b


if __name__ == "__main__":
		try:
				__A    :				Tuple    						=	int(input("""Enter Base : """).strip())
				__A    :				Any    						=	int(input("""Enter Power : """).strip())
		except ValueError:
				print("""Invalid literal for integer""")

		__A    :				Union[str, Any]    						=	binary_exponentiation(BASE, POWER)
		print(f'''{BASE}^({POWER}) : {RESULT}''')






