





import timeit







class 	_UpperCamelCase	:







					'''simple docstring'''

					def __init__(    self     :	List[Any]			,       __lowercase     :	List[Any]		):






						'''simple docstring'''







						if isinstance(__lowercase			,       __lowercase		):  # Initializes a matrix identical to the one provided.
							UpperCAmelCase_		    =  arg
							UpperCAmelCase_		    =  len(__lowercase		)
						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     :	Dict			,       __lowercase     :	int		):






						'''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  A_(      A					,   A ):
	UpperCAmelCase_		    =  Matrix([[1, 0], [0, 1]] )
	while b > 0:
		if b & 1:
			matrix *= a
		a *= a
		b >>= 1
	return matrix




def  A_(      A					,   A					,   A ):
	# Trivial Cases
	if n == 1:
		return fa
	elif n == 2:
		return fa
	UpperCAmelCase_		    =  Matrix([[1, 1], [1, 0]] )
	UpperCAmelCase_		    =  modular_exponentiation(A					,   n - 2 )
	return fa * matrix.t[0][0] + fa * matrix.t[0][1]




def  A_(      A					,   A					,   A ):
	# 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  A_(      ):
	UpperCAmelCase_		    =  """
from random import randint
from __main__ import fibonacci_with_matrix_exponentiation
"""
	UpperCAmelCase_		    =  """fibonacci_with_matrix_exponentiation(randint(1,70000), 1, 1)"""
	UpperCAmelCase_		    =  timeit.timeit(setup=A					,   stmt=A					,   number=100 )
	print("""With matrix exponentiation the average execution time is """					,   exec_time / 100 )
	return exec_time




def  A_(      ):
	UpperCAmelCase_		    =  """
from random import randint
from __main__ import simple_fibonacci
"""
	UpperCAmelCase_		    =  """simple_fibonacci(randint(1,70000), 1, 1)"""
	UpperCAmelCase_		    =  timeit.timeit(setup=A					,   stmt=A					,   number=100 )
	print(
	    """Without matrix exponentiation the average execution time is """					,   exec_time / 100 )
	return exec_time




def  A_(      ):
	matrix_exponentiation_time()
	simple_fibonacci_time()


if __name__ == "__main__":
				main()









def  A_(      A = 1000 ):
	UpperCAmelCase_		    =  0
	for i in range(A ):
		if i % 3 == 0 or i % 5 == 0:
			result += i
	return result


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


