
"""simple docstring"""
import timeit


class    _lowerCAmelCase						:



							def __init__(      self ,						a_   )							->							List[str]:
								if isinstance(a_ ,						a_   ):  # Initializes a matrix identical to the one provided.
									_UpperCAmelCase =						arg
									_UpperCAmelCase =						len(a_   )
								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 ,						a_   )							->							int:
								_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__      ):


	"""simple docstring"""






	_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__      ):


	"""simple docstring"""






	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__      ):


	"""simple docstring"""






	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  (		):


	"""simple docstring"""






	_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  (		):


	"""simple docstring"""






	_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  (		):


	"""simple docstring"""






	matrix_exponentiation_time()
	simple_fibonacci_time()


if __name__ == "__main__":
			main()






"""simple docstring"""
def     __lowerCamelCase  (		UpperCamelCase__ = 400_0000      ):


	"""simple docstring"""






	_UpperCAmelCase =						1
	_UpperCAmelCase =						2
	_UpperCAmelCase =						0
	while j <= n:
		if j % 2 == 0:
			total += j
		_UpperCAmelCase ,      _UpperCAmelCase =						j, i + j

	return total


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




