





"""simple docstring"""




def  a_       (							_lowercase ,		_lowercase     ):
						_UpperCamelCase    :      str						     =					[]
						_UpperCamelCase    :      int						     =					len(__lowerCamelCase     )
						for i in range(__lowerCamelCase     ):
												_UpperCamelCase    :      Union[str, Any]						     =					[]
												for j in range(__lowerCamelCase     ):
																		_UpperCamelCase    :      str						     =					0
																		for k in range(__lowerCamelCase     ):
																								_UpperCamelCase    :      str						     =					val + matrix_a[i][k] * matrix_b[k][j]
																		list_a.append(__lowerCamelCase     )
												matrix_c.append(__lowerCamelCase     )
						return matrix_c





def  a_       (							_lowercase     ):
						return [[int(row == column     ) for column in range(__lowerCamelCase     )] for row in range(__lowerCamelCase     )]





def  a_       (							_lowercase     ):
						if n <= 1:
												return n
						_UpperCamelCase    :      Tuple						     =					identity(2     )
						_UpperCamelCase    :      int						     =					[[1, 1], [1, 0]]
						_UpperCamelCase    :      Union[str, Any]						     =					n - 1
						while n > 0:
												if n % 2 == 1:
																		_UpperCamelCase    :      Optional[int]						     =					multiply(__lowerCamelCase ,		__lowerCamelCase     )
												_UpperCamelCase    :      int						     =					multiply(__lowerCamelCase ,		__lowerCamelCase     )
												_UpperCamelCase    :      Dict						     =					int(n / 2     )
						return res_matrix[0][0]





def  a_       (							_lowercase     ):
						if n <= 1:
												return n
						_UpperCamelCase    :      Optional[int]						     =					0
						_UpperCamelCase    :      List[Any]						     =					1
						for _ in range(2 ,		n + 1     ):
												_UpperCamelCase     ,							_UpperCamelCase    :      List[Any]						     =					fiba, fiba + fiba
						return fiba





def  a_       (							):
						for ordinal in "0th 1st 2nd 3rd 10th 100th 1000th".split():
												_UpperCamelCase    :      Tuple						     =					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"""




def  a_       (							_lowercase     ):
						return 1 if input_a == 0 else 0





def  a_       (							):
						assert not_gate(0     ) == 1
						assert not_gate(1     ) == 0


if __name__ == "__main__":
						print(not_gate(0))
						print(not_gate(1))



