






from functools import lru_cache





@lru_cache
def 						__UpperCAmelCase      (					a_):
							if not isinstance(a_							,					a_):
														raise TypeError('k must be an integer.')
							if k < 0:
														raise ValueError('k integer must be greater or equal to zero.')
							if k == 0:
														return 0
							elif k == 1:
														return 1
							else:
														return fibonacci(k - 1) + fibonacci(k - 2)





def 						__UpperCAmelCase      (					a_							,					a_):
							snake_case_           =							len(a_)
							# Find m such that F_m >= n where F_i is the i_th fibonacci number.
							snake_case_           =							0
							while True:
														if fibonacci(a_) >= len_list:
																					snake_case_           =							i
																					break
														i += 1
							snake_case_           =							0
							while fibb_k > 0:
														snake_case_           =							min(
														    offset + fibonacci(fibb_k - 1)							,					len_list - 1)  # Prevent out of range
														snake_case_           =							arr[index_k]
														if item_k_1 == val:
																					return index_k
														elif val < item_k_1:
																					fibb_k -= 1
														elif val > item_k_1:
																					offset += fibonacci(fibb_k - 1)
																					fibb_k -= 2
							else:
														return -1


if __name__ == "__main__":
	import doctest

	doctest.testmod()













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





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


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





