






import timeit




class        snake_case_					:

						"""simple docstring"""



						def __init__(self:				int   ,				__UpperCAmelCase:				Optional[Any]      )						->    Dict:




											'''simple docstring'''



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



						def __mul__(self:				Optional[int]   ,				__UpperCAmelCase:				Dict      )						->    str:




											'''simple docstring'''



											__a				:	Dict			=				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			)							->	Any:



					"""simple docstring"""
					__a				:	List[Any]			=				Matrix([[1, 0], [0, 1]]			)
					while b > 0:
										if b & 1:
															matrix *= a
										a *= a
										b >>= 1
					return matrix







def 						a_      (__A							,					__A							,					__A			)							->	Union[str, Any]:



					"""simple docstring"""
					# Trivial Cases
					if n == 1:
										return fa
					elif n == 2:
										return fa
					__a				:	List[str]			=				Matrix([[1, 1], [1, 0]]			)
					__a				:	Any			=				modular_exponentiation(__A							,					n - 2			)
					return fa * matrix.t[0][0] + fa * matrix.t[0][1]







def 						a_      (__A							,					__A							,					__A			)							->	Dict:



					"""simple docstring"""
					# Trivial Cases
					if n == 1:
										return fa
					elif n == 2:
										return fa

					__a				:	int			=				fa
					__a				:	List[str]			=				fa
					n -= 2

					while n > 0:
										__a			, __a				:	Optional[int]			=				fn_a + fn_a, fn_a
										n -= 1

					return fn_a







def 						a_      ()							->	Any:



					"""simple docstring"""
					__a				:	Optional[Any]			=				"\nfrom random import randint\nfrom __main__ import fibonacci_with_matrix_exponentiation\n"
					__a				:	int			=				"fibonacci_with_matrix_exponentiation(randint(1,70000), 1, 1)"
					__a				:	int			=				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_      ()							->	str:



					"""simple docstring"""
					__a				:	Any			=				"\nfrom random import randint\nfrom __main__ import simple_fibonacci\n"
					__a				:	Optional[int]			=				"simple_fibonacci(randint(1,70000), 1, 1)"
					__a				:	Any			=				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_      ()							->	int:



					"""simple docstring"""
					matrix_exponentiation_time()
					simple_fibonacci_time()


if __name__ == "__main__":
			main()













import math







def 						a_      (__A			)							->	bool:



					"""simple docstring"""

					if 1 < number < 4:
										# 2 and 3 are primes
										return True
					elif number < 2 or number % 2 == 0 or number % 3 == 0:
										# Negatives, 0, 1, all even numbers, all multiples of 3 are not primes
										return False

					# All primes number are in format of 6k +/- 1
					for i in range(5							,					int(math.sqrt(__A			) + 1			)							,					6			):
										if number % i == 0 or number % (i + 2) == 0:
															return False
					return True







def 						a_      (__A = 1_000							,					__A = 1_000			)							->	int:



					"""simple docstring"""
					__a				:	Optional[int]			=				[0, 0, 0]  # length, a, b
					for a in range((a_limit * -1) + 1							,					__A			):
										for b in range(2							,					__A			):
															if is_prime(__A			):
																				__a				:	Any			=				0
																				__a				:	List[str]			=				0
																				while is_prime((n**2) + (a * n) + b			):
																									count += 1
																									n += 1
																				if count > longest[0]:
																									__a				:	Any			=				[count, a, b]
					__a				:	str			=				longest[1] * longest[2]
					return ans


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





