

import timeit



class  __snake_case					:

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


  def __mul__(   self  ,						_A):
      SCREAMING_SNAKE_CASE_													=  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    (					_SCREAMING_SNAKE_CASE   :						Any	,				_SCREAMING_SNAKE_CASE   :						int    ):





    """simple docstring"""


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


def    _UpperCAmelCase    (					_SCREAMING_SNAKE_CASE   :						str	,				_SCREAMING_SNAKE_CASE   :						List[Any]	,				_SCREAMING_SNAKE_CASE   :						int    ):





    """simple docstring"""


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


def    _UpperCAmelCase    (					_SCREAMING_SNAKE_CASE   :						str	,				_SCREAMING_SNAKE_CASE   :						Union[str, Any]	,				_SCREAMING_SNAKE_CASE   :						Optional[int]    ):





    """simple docstring"""


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

    SCREAMING_SNAKE_CASE_													=  fa
    SCREAMING_SNAKE_CASE_													=  fa
    n -= 2

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

    return fn_a


def    _UpperCAmelCase    (					):





    """simple docstring"""


    SCREAMING_SNAKE_CASE_													=  '\nfrom random import randint\nfrom __main__ import fibonacci_with_matrix_exponentiation\n'
    SCREAMING_SNAKE_CASE_													=  'fibonacci_with_matrix_exponentiation(randint(1,70000), 1, 1)'
    SCREAMING_SNAKE_CASE_													=  timeit.timeit(setup=_SCREAMING_SNAKE_CASE	,				stmt=_SCREAMING_SNAKE_CASE	,				number=100    )
    print('With matrix exponentiation the average execution time is '	,				exec_time / 100    )
    return exec_time


def    _UpperCAmelCase    (					):





    """simple docstring"""


    SCREAMING_SNAKE_CASE_													=  '\nfrom random import randint\nfrom __main__ import simple_fibonacci\n'
    SCREAMING_SNAKE_CASE_													=  'simple_fibonacci(randint(1,70000), 1, 1)'
    SCREAMING_SNAKE_CASE_													=  timeit.timeit(setup=_SCREAMING_SNAKE_CASE	,				stmt=_SCREAMING_SNAKE_CASE	,				number=100    )
    print(
        'Without matrix exponentiation the average execution time is '	,				exec_time / 100    )
    return exec_time


def    _UpperCAmelCase    (					):





    """simple docstring"""


    matrix_exponentiation_time()
    simple_fibonacci_time()


if __name__ == "__main__":
       main()





def    _UpperCAmelCase    (					_SCREAMING_SNAKE_CASE   :						float	,				_SCREAMING_SNAKE_CASE   :						float    ):





    """simple docstring"""


    return a + b


if __name__ == "__main__":
       UpperCamelCase__					: Union[str, Any]								=      5
       UpperCamelCase__					: List[Any]								=      6
       print(F'The sum of {a} + {b} is {add(a, b)}')


