code: 
  
  
  
  
  
  import timeit
  
  
  
  
  
  class     __a						:
  
  
  
  
  
  
  
   def __init__(	self      :     Dict							,     SCREAMING_SNAKE_CASE      :     List[Any]		):
  
  
        '''simple docstring'''
  
  
  
  
  
  
        if isinstance(SCREAMING_SNAKE_CASE							,     SCREAMING_SNAKE_CASE		):  # Initializes a matrix identical to the one provided.
             UpperCamelCase__    :     Optional[int]        =						arg
             UpperCamelCase__    :     Tuple        =						len(SCREAMING_SNAKE_CASE		)
        else:  # Initializes a square matrix of the given size and set values to zero.
             UpperCamelCase__    :     List[str]        =						arg
             UpperCamelCase__    :     Tuple        =						[[0 for _ in range(self.n		)] for _ in range(self.n		)]
  
  
  
  
  
  
  
   def __mul__(	self      :     str							,     SCREAMING_SNAKE_CASE      :     int		):
  
  
        '''simple docstring'''
  
  
  
  
  
  
        UpperCamelCase__    :     Tuple        =						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 	SCREAMING_SNAKE_CASE							(      __lowerCAmelCase      ,					__lowerCAmelCase    )				->			int:
       UpperCamelCase__    :     Union[str, Any]        =						Matrix([[1, 0], [0, 1]]    )
       while b > 0:
            if b & 1:
                 matrix *= a
            a *= a
            b >>= 1
       return matrix
  
  
  
  
  
  
  
  def 	SCREAMING_SNAKE_CASE							(      __lowerCAmelCase      ,					__lowerCAmelCase      ,					__lowerCAmelCase    )				->			str:
       # Trivial Cases
       if n == 1:
            return fa
       elif n == 2:
            return fa
       UpperCamelCase__    :     str        =						Matrix([[1, 1], [1, 0]]    )
       UpperCamelCase__    :     Dict        =						modular_exponentiation(__lowerCAmelCase      ,					n - 2    )
       return fa * matrix.t[0][0] + fa * matrix.t[0][1]
  
  
  
  
  
  
  
  def 	SCREAMING_SNAKE_CASE							(      __lowerCAmelCase      ,					__lowerCAmelCase      ,					__lowerCAmelCase    )				->			Tuple:
       # Trivial Cases
       if n == 1:
            return fa
       elif n == 2:
            return fa
  
       UpperCamelCase__    :     Union[str, Any]        =						fa
       UpperCamelCase__    :     int        =						fa
       n -= 2
  
       while n > 0:
            UpperCamelCase__    :     Any        =						fn_a + fn_a, fn_a
            n -= 1
  
       return fn_a
  
  
  
  
  
  
  
  def 	SCREAMING_SNAKE_CASE							(      )				->			str:
       UpperCamelCase__    :     Any        =						"\nfrom random import randint\nfrom __main__ import fibonacci_with_matrix_exponentiation\n"
       UpperCamelCase__    :     Tuple        =						"fibonacci_with_matrix_exponentiation(randint(1,70000), 1, 1)"
       UpperCamelCase__    :     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 	SCREAMING_SNAKE_CASE							(      )				->			List[Any]:
       UpperCamelCase__    :     str        =						"\nfrom random import randint\nfrom __main__ import simple_fibonacci\n"
       UpperCamelCase__    :     str        =						"simple_fibonacci(randint(1,70000), 1, 1)"
       UpperCamelCase__    :     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 	SCREAMING_SNAKE_CASE							(      )				->			int:
       matrix_exponentiation_time()
       simple_fibonacci_time()
  
  
  if __name__ == "__main__":
   main()
style_context: 
  
  
  
  
  
  
  from __future__ import annotations
  
  
  
  
  
  
  
  def 	SCREAMING_SNAKE_CASE							(      __lowerCAmelCase    )				->			list[int]:
       assert (
           isinstance(__lowerCAmelCase      ,					__lowerCAmelCase    ) and mask > 0
       ), f'mask needs to be positive integer, your input {mask}'
       UpperCamelCase__    :     Any        =						[]
       UpperCamelCase__    :     int        =						mask
  
       while submask:
            all_submasks.append(__lowerCAmelCase    )
            UpperCamelCase__    :     List[str]        =						(submask - 1) & mask
  
       return all_submasks
  
  
  if __name__ == "__main__":
   import doctest
  
   doctest.testmod()