
'''simple docstring'''



def 				lowerCAmelCase_		(			SCREAMING_SNAKE_CASE_      , SCREAMING_SNAKE_CASE_  )       ->       list[list[int]]:




			"""simple docstring"""
			_SCREAMING_SNAKE_CASE       	=			[]
			_SCREAMING_SNAKE_CASE       	=			len(SCREAMING_SNAKE_CASE_  )
			for i in range(SCREAMING_SNAKE_CASE_  ):
						_SCREAMING_SNAKE_CASE       	=			[]
						for j in range(SCREAMING_SNAKE_CASE_  ):
									_SCREAMING_SNAKE_CASE       	=			0
									for k in range(SCREAMING_SNAKE_CASE_  ):
												_SCREAMING_SNAKE_CASE       	=			val + matrix_a[i][k] * matrix_b[k][j]
									list_a.append(SCREAMING_SNAKE_CASE_  )
						matrix_c.append(SCREAMING_SNAKE_CASE_  )
			return matrix_c
def 				lowerCAmelCase_		(			SCREAMING_SNAKE_CASE_  )       ->       list[list[int]]:




			"""simple docstring"""
			return [[int(row == column  ) for column in range(SCREAMING_SNAKE_CASE_  )] for row in range(SCREAMING_SNAKE_CASE_  )]
def 				lowerCAmelCase_		(			SCREAMING_SNAKE_CASE_  )       ->       int:




			"""simple docstring"""
			if n <= 1:
						return n
			_SCREAMING_SNAKE_CASE       	=			identity(2  )
			_SCREAMING_SNAKE_CASE       	=			[[1, 1], [1, 0]]
			_SCREAMING_SNAKE_CASE       	=			n - 1
			while n > 0:
						if n % 2 == 1:
									_SCREAMING_SNAKE_CASE       	=			multiply(SCREAMING_SNAKE_CASE_      , SCREAMING_SNAKE_CASE_  )
						_SCREAMING_SNAKE_CASE       	=			multiply(SCREAMING_SNAKE_CASE_      , SCREAMING_SNAKE_CASE_  )
						_SCREAMING_SNAKE_CASE       	=			int(n / 2  )
			return res_matrix[0][0]
def 				lowerCAmelCase_		(			SCREAMING_SNAKE_CASE_  )       ->       int:




			"""simple docstring"""
			if n <= 1:
						return n
			_SCREAMING_SNAKE_CASE       	=			0
			_SCREAMING_SNAKE_CASE       	=			1
			for _ in range(2      , n + 1  ):
						_SCREAMING_SNAKE_CASE	,							_SCREAMING_SNAKE_CASE       	=			fiba, fiba + fiba
			return fiba
def 				lowerCAmelCase_		(			)       ->       None:




			"""simple docstring"""
			for ordinal in "0th 1st 2nd 3rd 10th 100th 1000th".split():
						_SCREAMING_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(SCREAMING_SNAKE_CASE_  )} and using bruteforce is "
						    F"{nth_fibonacci_bruteforce(SCREAMING_SNAKE_CASE_  )}\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 				lowerCAmelCase_		(			SCREAMING_SNAKE_CASE_  )       ->       str:




   """simple docstring"""
   return " ".join(sorted(set(sentence.split()  )  )  )


if __name__ == "__main__":
     import doctest

     doctest.testmod()






