



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



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



def  _lowerCAmelCase     (_lowerCAmelCase):
					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(_lowerCAmelCase ,						_lowerCAmelCase)
										UpperCamelCase_			= multiply(_lowerCAmelCase ,						_lowerCAmelCase)
										UpperCamelCase_			= int(n / 2)
					return res_matrix[0][0]



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



def  _lowerCAmelCase     ():
					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(_lowerCAmelCase)} and using bruteforce is """
										    f"""{nth_fibonacci_bruteforce(_lowerCAmelCase)}\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()





UpperCAmelCase :				Optional[int]							="""
# Diffusers installation
! pip install diffusers transformers datasets accelerate
# To install from source instead of the last release, comment the command above and uncomment the following one.
# ! pip install git+https://github.com/huggingface/diffusers.git
"""

UpperCAmelCase :				List[Any]							=[{"""type""": """code""", """content""": INSTALL_CONTENT}]
