





import timeit

class 					__A   :


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


				def __mul__(						self      ,       UpperCAmelCase_							):
								lowerCamelCase		       =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    _lowercase    (  _UpperCAmelCase	,					_UpperCAmelCase )  ->     Union[str, Any]:
				lowerCamelCase		       =Matrix([[1, 0], [0, 1]] )
				while b > 0:
								if b & 1:
												matrix *= a
								a *= a
								b >>= 1
				return matrix





def    _lowercase    (  _UpperCAmelCase	,					_UpperCAmelCase	,					_UpperCAmelCase )  ->     Any:


				if n == 1:
								return fa
				elif n == 2:
								return fa
				lowerCamelCase		       =Matrix([[1, 1], [1, 0]] )
				lowerCamelCase		       =modular_exponentiation(_SCREAMING_SNAKE_CASE	,					n - 2 )
				return fa * matrix.t[0][0] + fa * matrix.t[0][1]





def    _lowercase    (  _UpperCAmelCase	,					_UpperCAmelCase	,					_UpperCAmelCase )  ->     Optional[Any]:


				if n == 1:
								return fa
				elif n == 2:
								return fa

				lowerCamelCase		       =fa
				lowerCamelCase		       =fa
				n -= 2

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

				return fn_a





def    _lowercase    (  )  ->     str:
				lowerCamelCase		       ="""\nfrom random import randint\nfrom __main__ import fibonacci_with_matrix_exponentiation\n"""
				lowerCamelCase		       ="""fibonacci_with_matrix_exponentiation(randint(1,70000), 1, 1)"""
				lowerCamelCase		       =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    _lowercase    (  )  ->     Optional[int]:
				lowerCamelCase		       ="""\nfrom random import randint\nfrom __main__ import simple_fibonacci\n"""
				lowerCamelCase		       ="""simple_fibonacci(randint(1,70000), 1, 1)"""
				lowerCamelCase		       =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    _lowercase    (  )  ->     Dict:
				matrix_exponentiation_time()
				simple_fibonacci_time()


if __name__ == "__main__":
							main()








from itertools import permutations


def     _UpperCAmelCase				(     ):





    """simple docstring"""


    SCREAMING_SNAKE_CASE_													=  list(map(''.join       ,      permutations('0123456789'				)				)				)
    return result[999_999]


if __name__ == "__main__":
       print(solution())


