


def 			_a      (    __UpperCamelCase	,	__UpperCamelCase			):
     a_     :  List[Any]				      =     []
     a_     :  List[Any]				      =     len(__UpperCamelCase			)
     for i in range(__UpperCamelCase			):
          a_     :  Any				      =     []
          for j in range(__UpperCamelCase			):
               a_     :  Tuple				      =     0
               for k in range(__UpperCamelCase			):
                    a_     :  Union[str, Any]				      =     val + matrix_a[i][k] * matrix_b[k][j]
               list_a.append(__UpperCamelCase			)
          matrix_c.append(__UpperCamelCase			)
     return matrix_c



def 			_a      (    __UpperCamelCase			):
     return [[int(row == column			) for column in range(__UpperCamelCase			)] for row in range(__UpperCamelCase			)]



def 			_a      (    __UpperCamelCase			):






     if n <= 1:
          return n
     a_     :  List[Any]				      =     identity(2			)
     a_     :  Optional[int]				      =     [[1, 1], [1, 0]]
     a_     :  List[Any]				      =     n - 1
     while n > 0:
          if n % 2 == 1:
               a_     :  List[str]				      =     multiply(__UpperCamelCase	,	__UpperCamelCase			)
          a_     :  Any				      =     multiply(__UpperCamelCase	,	__UpperCamelCase			)
          a_     :  List[str]				      =     int(n / 2			)
     return res_matrix[0][0]



def 			_a      (    __UpperCamelCase			):






     if n <= 1:
          return n
     a_     :  Union[str, Any]				      =     0
     a_     :  int				      =     1
     for _ in range(2	,	n + 1			):
          a_      ,      a_     :  Tuple				      =     fiba, fiba + fiba
     return fiba



def 			_a      (    ):






     for ordinal in "0th 1st 2nd 3rd 10th 100th 1000th".split():
          a_     :  Optional[Any]				      =     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(__UpperCamelCase			)} and using bruteforce is '''
              F'''{nth_fibonacci_bruteforce(__UpperCamelCase			)}\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'''

class __magic_name__:






						def __init__(   self						:						List[Any]       ):



									'''simple docstring'''






									snake_case__          =						[]
									snake_case__          =						0
									snake_case__          =						0






						def __str__(   self						:						Union[str, Any]       ):



									'''simple docstring'''






									snake_case__          =						"""<""" + str(self.entries       )[1:-1] + """>"""
									return printed






						def       __lowerCAmelCase(   self						:						List[Any]					,   __UpperCamelCase						:						List[Any]       ):



									'''simple docstring'''






									self.entries.append(__UpperCamelCase       )
									snake_case__          =						self.length + 1






						def       __lowerCAmelCase(   self						:						int       ):



									'''simple docstring'''






									snake_case__          =						self.length - 1
									snake_case__          =						self.entries[self.front]
									# self.front-=1
									# self.entries = self.entries[self.front:]
									snake_case__          =						self.entries[1:]
									return dequeued






						def       __lowerCAmelCase(   self						:						str					,   __UpperCamelCase						:						Optional[Any]       ):



									'''simple docstring'''






									for _ in range(__UpperCamelCase       ):
												self.put(self.get()       )






						def       __lowerCAmelCase(   self						:						List[Any]       ):



									'''simple docstring'''






									return self.entries[0]






						def       __lowerCAmelCase(   self						:						str       ):



									'''simple docstring'''






									return self.length