





'''simple docstring'''
def     lowercase__       (       __lowercase						:  list[list[int]]    ,  __lowercase						:  list[list[int]]					)			->				list[list[int]]:



       """simple docstring"""






       __UpperCamelCase	=  []
       __UpperCamelCase	=  len(__lowercase					)
       for i in range(__lowercase					):
              __UpperCamelCase	=  []
              for j in range(__lowercase					):
                     __UpperCamelCase	=  0
                     for k in range(__lowercase					):
                            __UpperCamelCase	=  val + matrix_a[i][k] * matrix_b[k][j]
                     list_a.append(__lowercase					)
              matrix_c.append(__lowercase					)
       return matrix_c
def     lowercase__       (       __lowercase						:  int					)			->				list[list[int]]:



       """simple docstring"""






       return [[int(row == column					) for column in range(__lowercase					)] for row in range(__lowercase					)]
def     lowercase__       (       __lowercase						:  int					)			->				int:



       """simple docstring"""






       if n <= 1:
              return n
       __UpperCamelCase	=  identity(2					)
       __UpperCamelCase	=  [[1, 1], [1, 0]]
       __UpperCamelCase	=  n - 1
       while n > 0:
              if n % 2 == 1:
                     __UpperCamelCase	=  multiply(__lowercase    ,  __lowercase					)
              __UpperCamelCase	=  multiply(__lowercase    ,  __lowercase					)
              __UpperCamelCase	=  int(n / 2					)
       return res_matrix[0][0]
def     lowercase__       (       __lowercase						:  int					)			->				int:



       """simple docstring"""






       if n <= 1:
              return n
       __UpperCamelCase	=  0
       __UpperCamelCase	=  1
       for _ in range(2    ,  n + 1					):
              __UpperCamelCase	,						__UpperCamelCase	=  fiba, fiba + fiba
       return fiba
def     lowercase__       (       )			->				None:



       """simple docstring"""






       for ordinal in "0th 1st 2nd 3rd 10th 100th 1000th".split():
              __UpperCamelCase	=  int(''.join(c for c in ordinal if c in '0123456789'					)					)  # 1000th --> 1000
              print(
                  F'''{ordinal} fibonacci number using matrix exponentiation is '''
                  F'''{nth_fibonacci_matrix(__lowercase					)} and using bruteforce is '''
                  F'''{nth_fibonacci_bruteforce(__lowercase					)}\n'''					)
       # from timeit import timeit
       # print(timeit("nth_fibonacci_matrix(1000000)",
       #              "from main import nth_fibonacci_matrix", number=5))
       # print(timeit("nth_fibonacci_bruteforce(1000000)",
       #              "from main import nth_fibonacci_bruteforce", number=5))
       # 2.3342058970001744
       # 57.256506615000035


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    main()







'''simple docstring'''
def     lowercase__       (       __lowercase						:  list    ,  __lowercase						:  int    ,  __lowercase						:  int    ,  __lowercase						:  int					)			->				int:



       """simple docstring"""






       __UpperCamelCase	=  int((lower_bound + upper_bound) // 2					)
       if array[r] == value:
              return r
       if lower_bound >= upper_bound:
              return -1
       if array[r] < value:
              return binary_search(__lowercase    ,  r + 1    ,  __lowercase    ,  __lowercase					)
       else:
              return binary_search(__lowercase    ,  __lowercase    ,  r - 1    ,  __lowercase					)
def     lowercase__       (       __lowercase						:  int    ,  __lowercase						:  list					)			->				list:



       """simple docstring"""






       __UpperCamelCase	=  0
       if matrix[index][0] == value:
              return [index, 0]
       while index < len(__lowercase					) and matrix[index][0] < value:
              __UpperCamelCase	=  binary_search(matrix[index]    ,  0    ,  len(matrix[index]					) - 1    ,  __lowercase					)
              if r != -1:
                     return [index, r]
              index += 1
       return [-1, -1]


if __name__ == "__main__":
    import doctest

    doctest.testmod()
