"""simple docstring"""







def 					a__ (						UpperCAmelCase__    :     list[list[int]]						,     UpperCAmelCase__    :     list[list[int]]     )->		list[list[int]]:
						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 					a__ (						UpperCAmelCase__    :     int     )->		list[list[int]]:
						return [[int(row == column     ) for column in range(_lowerCamelCase     )] for row in range(_lowerCamelCase     )]


def 					a__ (						UpperCAmelCase__    :     int     )->		int:





						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 					a__ (						UpperCAmelCase__    :     int     )->		int:





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


def 					a__ (						)->		None:





						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()


"""simple docstring"""







from __future__ import annotations


def 					a__ (						UpperCAmelCase__    :     int     )->		list[int]:
						assert (
						    isinstance(UpperCAmelCase__						,     UpperCAmelCase__     ) and mask > 0
						), f'mask needs to be positive integer, your input {mask}'
						UpperCAmelCase__   		=						[]
						UpperCAmelCase__   		=						mask

						while submask:
												all_submasks.append(UpperCAmelCase__     )
												UpperCAmelCase__   		=						(submask - 1) & mask

						return all_submasks


if __name__ == "__main__":
						import doctest

						doctest.testmod()

