

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    :						Optional[Any]       ,      _SCREAMING_SNAKE_CASE    :						List[str]				):





    """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    :						Optional[Any]       ,      _SCREAMING_SNAKE_CASE    :						Optional[Any]       ,      _SCREAMING_SNAKE_CASE    :						Optional[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    :						Optional[Any]       ,      _SCREAMING_SNAKE_CASE    :						Optional[int]       ,      _SCREAMING_SNAKE_CASE    :						List[Any]				):





    """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()





from itertools import permutations


def     _UpperCAmelCase				(     ):





    """simple docstring"""


    SCREAMING_SNAKE_CASE_													=  list(map(''.join       ,      permutations('0123456789'				)				)				)
    return result[999_999]


if __name__ == "__main__":
       print(solution())


