




'''simple docstring'''





import timeit






class 						lowercase     :






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






      def __mul__(self ,  a__					)       ->   List[Any]:
         SCREAMING_SNAKE_CASE__			:				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 				UpperCamelCase	(  snake_case	,     snake_case   ):




   '''simple docstring'''

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


def 				UpperCamelCase	(  snake_case	,     snake_case	,     snake_case   ):




   '''simple docstring'''

   if n == 1:
      return fa
   elif n == 2:
      return fa
   SCREAMING_SNAKE_CASE__			:				str       						= Matrix([[1, 1], [1, 0]]   )
   SCREAMING_SNAKE_CASE__			:				Optional[int]       						= modular_exponentiation(snake_case	,     n - 2   )
   return fa * matrix.t[0][0] + fa * matrix.t[0][1]


def 				UpperCamelCase	(  snake_case	,     snake_case	,     snake_case   ):




   '''simple docstring'''

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

   SCREAMING_SNAKE_CASE__			:				Tuple       						= fa
   SCREAMING_SNAKE_CASE__			:				List[Any]       						= fa
   n -= 2

   while n > 0:
      SCREAMING_SNAKE_CASE__			:				Any       						= fn_a + fn_a, fn_a
      n -= 1

   return fn_a


def 				UpperCamelCase	(  ):




   '''simple docstring'''

   SCREAMING_SNAKE_CASE__			:				Optional[Any]       						= '''
from random import randint
from __main__ import fibonacci_with_matrix_exponentiation
'''
   SCREAMING_SNAKE_CASE__			:				Union[str, Any]       						= '''fibonacci_with_matrix_exponentiation(randint(1,70000), 1, 1)'''
   SCREAMING_SNAKE_CASE__			:				str       						= timeit.timeit(setup=snake_case	,     stmt=snake_case	,     number=1_00   )
   print('''With matrix exponentiation the average execution time is '''	,     exec_time / 1_00   )
   return exec_time


def 				UpperCamelCase	(  ):




   '''simple docstring'''

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


def 				UpperCamelCase	(  ):




   '''simple docstring'''

   matrix_exponentiation_time()
   simple_fibonacci_time()


if __name__ == "__main__":
       main()







'''simple docstring'''





def 				UpperCamelCase	(  snake_case = 99_80_01   ):




   '''simple docstring'''

   for number in range(n - 1	,     99_99	,     -1   ):
      SCREAMING_SNAKE_CASE__			:				int       						= str(snake_case   )

      # checks whether 'str_number' is a palindrome.
      if str_number == str_number[::-1]:
         SCREAMING_SNAKE_CASE__			:				Any       						= 9_99

         # if 'number' is a product of two 3-digit numbers
         # then number is the answer otherwise fetch next number.
         while divisor != 99:
            if (number % divisor == 0) and (len(str(number // divisor   )   ) == 3.0):
               return number
            divisor -= 1
   raise ValueError('''That number is larger than our acceptable range.'''   )


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

