"""simple docstring"""


import timeit






class  a__     :


   def __init__(  self,					_UpperCAmelCase	):
        '''simple docstring'''



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


   def __mul__(  self,					_UpperCAmelCase	):
        '''simple docstring'''



        lowercase__								=				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   ):






     '''simple docstring'''



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







def        __a (		A     ,					A     ,					A   ):






     '''simple docstring'''



     if n == 1:
          return fa
     elif n == 2:
          return fa
     lowercase__								=				Matrix([[1, 1], [1, 0]]   )
     lowercase__								=				modular_exponentiation(A     ,					n - 2   )
     return fa * matrix.t[0][0] + fa * matrix.t[0][1]







def        __a (		A     ,					A     ,					A   ):






     '''simple docstring'''



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

     lowercase__								=				fa
     lowercase__								=				fa
     n -= 2

     while n > 0:
          lowercase__			,    lowercase__								=				fn_a + fn_a, fn_a
          n -= 1

     return fn_a







def        __a (		):






     '''simple docstring'''



     lowercase__								=				"\nfrom random import randint\nfrom __main__ import fibonacci_with_matrix_exponentiation\n"
     lowercase__								=				"fibonacci_with_matrix_exponentiation(randint(1,70000), 1, 1)"
     lowercase__								=				timeit.timeit(setup=A     ,					stmt=A     ,					number=1_00   )
     print("With matrix exponentiation the average execution time is "     ,					exec_time / 1_00   )
     return exec_time







def        __a (		):






     '''simple docstring'''



     lowercase__								=				"\nfrom random import randint\nfrom __main__ import simple_fibonacci\n"
     lowercase__								=				"simple_fibonacci(randint(1,70000), 1, 1)"
     lowercase__								=				timeit.timeit(setup=A     ,					stmt=A     ,					number=1_00   )
     print(
         "Without matrix exponentiation the average execution time is "     ,					exec_time / 1_00   )
     return exec_time







def        __a (		):






     '''simple docstring'''



     matrix_exponentiation_time()
     simple_fibonacci_time()


if __name__ == "__main__":
 main()





"""simple docstring"""


def        __a (		A     ,					A   ):






     '''simple docstring'''



     lowercase__								=				sorted(A     ,					key=lambda A   : value[2]     ,					reverse=A   )

     # Create a list of size equal to the maximum deadline
     # and initialize it with -1
     lowercase__								=				max(A     ,					key=lambda A   : value[1]   )[1]
     lowercase__								=				[-1] * max_deadline

     # Finding the maximum profit and the count of jobs
     lowercase__								=				0
     lowercase__								=				0
     for job in jobs:
          # Find a free time slot for this job
          # (Note that we start from the last possible slot)
          for i in range(job[1] - 1     ,					-1     ,					-1   ):
               if time_slots[i] == -1:
                    lowercase__								=				job[0]
                    count += 1
                    max_profit += job[2]
                    break
     return [count, max_profit]


if __name__ == "__main__":
 import doctest

 doctest.testmod()




