from functools import lru_cache





@lru_cache
def 	lowerCAmelCase_			(					__lowerCAmelCase    )->	int:






      '''simple docstring'''





      if not isinstance(__lowerCAmelCase		,       __lowerCAmelCase    ):
            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 	lowerCAmelCase_			(					__lowerCAmelCase		,       __lowerCAmelCase    )->	int:






      '''simple docstring'''





      UpperCAmelCase     :			Dict     	=len(__lowerCAmelCase    )
      # Find m such that F_m >= n where F_i is the i_th fibonacci number.
      UpperCAmelCase     :			List[str]     	=0
      while True:
            if fibonacci(__lowerCAmelCase    ) >= len_list:
                  UpperCAmelCase     :			Optional[int]     	=i
                  break
            i += 1
      UpperCAmelCase     :			Any     	=0
      while fibb_k > 0:
            UpperCAmelCase     :			Optional[int]     	=min(
                offset + fibonacci(fibb_k - 1    )		,       len_list - 1    )  # Prevent out of range
            UpperCAmelCase     :			int     	=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()

from hashlib import mda, shaaaa

__snake_case         =     (shaaaa, mda)







class       __snake_case :
 def __init__(	self		, snake_case__ = 8    )						->				None:
       '''simple docstring'''





       UpperCAmelCase     :			str     	=0b0
       UpperCAmelCase     :			str     	=size
 def 						UpperCAmelCase__							(	self		, snake_case__    )						->				None:
       '''simple docstring'''





       UpperCAmelCase     :			Union[str, Any]     	=self.hash_(snake_case__    )
       self.bitarray |= h
 def 						UpperCAmelCase__							(	self		, snake_case__    )						->				bool:
       '''simple docstring'''





       UpperCAmelCase     :			List[Any]     	=self.hash_(snake_case__    )
       return (h & self.bitarray) == h
 def __contains__(	self		, snake_case__    )						->				bool:
       '''simple docstring'''





       return self.exists(snake_case__    )
 def 						UpperCAmelCase__							(	self		, snake_case__    )						->				str:
       '''simple docstring'''





       UpperCAmelCase     :			Dict     	=bin(snake_case__    )[2:]
       return res.zfill(self.size    )
 @property
 def 						UpperCAmelCase__							(	self    )						->				str:
       '''simple docstring'''





       return self.format_bin(self.bitarray    )
 def 						UpperCAmelCase__							(	self		, snake_case__    )						->				int:
       '''simple docstring'''





       UpperCAmelCase     :			Union[str, Any]     	=0b0
       for func in HASH_FUNCTIONS:
             UpperCAmelCase     :			Optional[Any]     	=(
                 int.from_bytes(func(value.encode()    ).digest()		, '''little'''    ) % self.size
             )
             res |= 2**position
       return res
 def 						UpperCAmelCase__							(	self		, snake_case__    )						->				str:
       '''simple docstring'''





       return self.format_bin(self.hash_(snake_case__    )    )






 @property
 def 						UpperCAmelCase__							(	self    )						->				float:
       '''simple docstring'''





       UpperCAmelCase     :			int     	=bin(self.bitarray    ).count('''1'''    )
       return (n_ones / self.size) ** len(snake_case__    )
