





'''simple docstring'''






import timeit



class  lowerCamelCase__				:


	"""simple docstring"""





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




	def __mul__(					self   ,     UpperCAmelCase__			)       ->				str:
					_A :				Union[str, Any]				=  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  (  lowerCAmelCase :						List[str]   , lowerCAmelCase :						Any):



				"""simple docstring"""


				_A :				Optional[Any]				=  Matrix([[1, 0], [0, 1]])
				while b > 0:
								if b & 1:
												matrix *= a
								a *= a
								b >>= 1
				return matrix





def      lowercase  (  lowerCAmelCase :						List[Any]   , lowerCAmelCase :						str   , lowerCAmelCase :						Dict):



				"""simple docstring"""


				if n == 1:
								return fa
				elif n == 2:
								return fa
				_A :				str				=  Matrix([[1, 1], [1, 0]])
				_A :				Union[str, Any]				=  modular_exponentiation(lowerCAmelCase   , n - 2)
				return fa * matrix.t[0][0] + fa * matrix.t[0][1]





def      lowercase  (  lowerCAmelCase :						Dict   , lowerCAmelCase :						List[Any]   , lowerCAmelCase :						Tuple):



				"""simple docstring"""


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

				_A :				Optional[Any]				=  fa
				_A :				int				=  fa
				n -= 2

				while n > 0:
								_A	,       _A :				Dict				=  fn_a + fn_a, fn_a
								n -= 1

				return fn_a





def      lowercase  (  ):



				"""simple docstring"""


				_A :				Optional[int]				=  '''
from random import randint
from __main__ import fibonacci_with_matrix_exponentiation
'''
				_A :				int				=  '''fibonacci_with_matrix_exponentiation(randint(1,70000), 1, 1)'''
				_A :				Any				=  timeit.timeit(setup=lowerCAmelCase   , stmt=lowerCAmelCase   , number=100)
				print('''With matrix exponentiation the average execution time is '''   , exec_time / 100)
				return exec_time





def      lowercase  (  ):



				"""simple docstring"""


				_A :				Any				=  '''
from random import randint
from __main__ import simple_fibonacci
'''
				_A :				Optional[int]				=  '''simple_fibonacci(randint(1,70000), 1, 1)'''
				_A :				Union[str, Any]				=  timeit.timeit(setup=lowerCAmelCase   , stmt=lowerCAmelCase   , number=100)
				print(
				    '''Without matrix exponentiation the average execution time is '''   , exec_time / 100)
				return exec_time





def      lowercase  (  ):



				"""simple docstring"""


				matrix_exponentiation_time()
				simple_fibonacci_time()


if __name__ == "__main__":
	main()







'''simple docstring'''






import sys

sys.set_int_max_str_digits(0)  # type: ignore





def      lowercase  (  lowerCAmelCase :						int):



				"""simple docstring"""


				_A :				List[Any]				=  [0] * 11
				_A :				Optional[Any]				=  [0] * 11

				# mark last 9 numbers
				for _ in range(9):
								_A :				Dict				=  1
								_A :				Optional[int]				=  number // 10
				# flag
				_A :				str				=  True

				# check last 9 numbers for pandigitality

				for x in range(9):
								if not check_last[x + 1]:
												_A :				Dict				=  False
				if not f:
								return f

				# mark first 9 numbers
				_A :				str				=  int(str(lowerCAmelCase)[:9])

				for _ in range(9):
								_A :				Tuple				=  1
								_A :				Union[str, Any]				=  number // 10

				# check first 9 numbers for pandigitality

				for x in range(9):
								if not check_front[x + 1]:
												_A :				Union[str, Any]				=  False
				return f





def      lowercase  (  lowerCAmelCase :						int):



				"""simple docstring"""


				_A :				Tuple				=  [0] * 11

				# mark last 9 numbers
				for _ in range(9):
								_A :				int				=  1
								_A :				Optional[int]				=  number // 10
				# flag
				_A :				List[str]				=  True

				# check last 9 numbers for pandigitality

				for x in range(9):
								if not check_last[x + 1]:
												_A :				Any				=  False
				return f





def      lowercase  (  ):



				"""simple docstring"""


				_A :				Union[str, Any]				=  1
				_A :				Tuple				=  1
				_A :				List[str]				=  2
				# temporary Fibonacci numbers

				_A :				List[str]				=  1
				_A :				str				=  1
				_A :				List[str]				=  2
				# temporary Fibonacci numbers mod 1e9

				# mod m=1e9, done for fast optimisation
				_A :				Any				=  [0] * 100_0000
				_A :				List[Any]				=  10_0000_0000

				for x in range(100_0000):
								_A :				Dict				=  (aa + ba) % m
								_A :				str				=  ba % m
								_A :				Union[str, Any]				=  ca % m
								if checka(lowerCAmelCase):
												_A :				List[str]				=  1

				for x in range(100_0000):
								_A :				str				=  a + b
								_A :				List[str]				=  b
								_A :				int				=  c
								# perform check only if in tocheck
								if tocheck[x + 3] and check(lowerCAmelCase):
												return x + 3  # first 2 already done
				return -1


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