




'''simple docstring'''

def    snake_case__     (  a       ,      a	)			->       list[list[int]]:





			'''simple docstring'''






			snake_case__          =						[]
			snake_case__          =						len(a	)
			for i in range(a	):
						snake_case__          =						[]
						for j in range(a	):
									snake_case__          =						0
									for k in range(a	):
												snake_case__          =						val + matrix_a[i][k] * matrix_b[k][j]
									list_a.append(a	)
						matrix_c.append(a	)
			return matrix_c




def    snake_case__     (  a	)			->       list[list[int]]:





			'''simple docstring'''






			return [[int(row == column	) for column in range(a	)] for row in range(a	)]




def    snake_case__     (  a	)			->       int:





			'''simple docstring'''






			if n <= 1:
						return n
			snake_case__          =						identity(2	)
			snake_case__          =						[[1, 1], [1, 0]]
			snake_case__          =						n - 1
			while n > 0:
						if n % 2 == 1:
									snake_case__          =						multiply(a       ,      a	)
						snake_case__          =						multiply(a       ,      a	)
						snake_case__          =						int(n / 2	)
			return res_matrix[0][0]




def    snake_case__     (  a	)			->       int:





			'''simple docstring'''






			if n <= 1:
						return n
			snake_case__          =						0
			snake_case__          =						1
			for _ in range(2       ,      n + 1	):
						snake_case__    ,			snake_case__          =						fiba, fiba + fiba
			return fiba




def    snake_case__     (  )			->       None:





			'''simple docstring'''






			for ordinal in "0th 1st 2nd 3rd 10th 100th 1000th".split():
						snake_case__          =						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(a	)} and using bruteforce is """
						    F"""{nth_fibonacci_bruteforce(a	)}\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       lowerCamelCase_		:





				"""simple docstring"""







				class       lowerCamelCase_		:





								"""simple docstring"""







								_lowerCAmelCase   :   Dict   				=       "_prev", "_data", "_next"



								def __init__(    self							,		UpperCAmelCase__							,		UpperCAmelCase__							,		UpperCAmelCase__  ):
												SCREAMING_SNAKE_CASE__  				=					link_p
												SCREAMING_SNAKE_CASE__  				=					element
												SCREAMING_SNAKE_CASE__  				=					link_n






								def 	lowerCAmelCase__		(    self  ):
												return (
												    f''' Prev -> {self._prev is not None}, Next -> {self._next is not None}'''
												)



				def __init__(    self  ):
								SCREAMING_SNAKE_CASE__  				=					self._Node(UpperCAmelCase__							,		UpperCAmelCase__							,		UpperCAmelCase__  )
								SCREAMING_SNAKE_CASE__  				=					self._Node(UpperCAmelCase__							,		UpperCAmelCase__							,		UpperCAmelCase__  )
								SCREAMING_SNAKE_CASE__  				=					self._trailer
								SCREAMING_SNAKE_CASE__  				=					self._header
								SCREAMING_SNAKE_CASE__  				=					0



				def __len__(    self  ):
								return self._size



				def 	lowerCAmelCase__		(    self  ):
								return self.__len__() == 0



				def 	lowerCAmelCase__		(    self							,		UpperCAmelCase__							,		UpperCAmelCase__							,		UpperCAmelCase__  ):
								# Create new_node by setting it's prev.link -> header
								# setting it's next.link -> trailer
								SCREAMING_SNAKE_CASE__  				=					self._Node(UpperCAmelCase__							,		UpperCAmelCase__							,		UpperCAmelCase__  )
								SCREAMING_SNAKE_CASE__  				=					new_node
								SCREAMING_SNAKE_CASE__  				=					new_node
								self._size += 1
								return self






				def 	lowerCAmelCase__		(    self							,		UpperCAmelCase__  ):
								SCREAMING_SNAKE_CASE__  				=					node._prev
								SCREAMING_SNAKE_CASE__  				=					node._next

								SCREAMING_SNAKE_CASE__  				=					successor
								SCREAMING_SNAKE_CASE__  				=					predecessor
								self._size -= 1
								SCREAMING_SNAKE_CASE__  				=					node._data
								SCREAMING_SNAKE_CASE__  				=					SCREAMING_SNAKE_CASE__  				=					SCREAMING_SNAKE_CASE__  				=					None
								del node
								return temp


class       lowerCamelCase_		(      _DoublyLinkedBase ):





				"""simple docstring"""







				def 	lowerCAmelCase__		(    self  ):
								if self.is_empty():
												raise Exception("List is empty"  )
								return self._header._next._data



				def 	lowerCAmelCase__		(    self  ):
								if self.is_empty():
												raise Exception("List is empty"  )
								return self._trailer._prev._data



				def 	lowerCAmelCase__		(    self							,		UpperCAmelCase__  ):
								return self._insert(self._header							,		UpperCAmelCase__							,		self._header._next  )



				def 	lowerCAmelCase__		(    self							,		UpperCAmelCase__  ):
								return self._insert(self._trailer._prev							,		UpperCAmelCase__							,		self._trailer  )



				def 	lowerCAmelCase__		(    self  ):
								if self.is_empty():
												raise IndexError("remove_first from empty list"  )
								return self._delete(self._header._next  )






				def 	lowerCAmelCase__		(    self  ):
								if self.is_empty():
												raise IndexError("remove_first from empty list"  )
								return self._delete(self._trailer._prev  )
