





"""simple docstring"""






from collections.abc import Iterator, MutableMapping
from dataclasses import dataclass
from typing import Generic, TypeVar

A 			=  TypeVar('''KEY''')
A 			=  TypeVar('''VAL''')




@dataclass(frozen=UpperCAmelCase_   ,      slots=UpperCAmelCase_							)
class 				__lowercase			(			Generic[KEY, VAL]							):







					'''simple docstring'''




					__lowerCAmelCase  =  42
					__lowerCAmelCase  =  42






class 				__lowercase			(			_Item							):







					'''simple docstring'''




					def __init__(						self     ):
									super().__init__(_lowercase	,			_lowercase     )







					def __bool__(						self     ):
									return False






A 			=  _DeletedItem()




class 				__lowercase			(			MutableMapping[KEY, VAL]							):







					'''simple docstring'''




					def __init__(						self	,			_UpperCAmelCase = 8	,			_UpperCAmelCase = 0.7_5     ):
									__a :						Dict			       =  initial_block_size
									__a :						list[_Item | None]			       =  [None] * initial_block_size
									assert 0.0 < capacity_factor < 1.0
									__a :						List[str]			       =  capacity_factor
									__a :						Optional[Any]			       =  0







					def  _lowerCamelCase		(						self	,			_UpperCAmelCase     ):
									return hash(_lowercase     ) % len(self._buckets     )







					def  _lowerCamelCase		(						self	,			_UpperCAmelCase     ):
									return (ind + 1) % len(self._buckets     )







					def  _lowerCamelCase		(						self	,			_UpperCAmelCase	,			_UpperCAmelCase	,			_UpperCAmelCase     ):
									__a :						List[str]			       =  self._buckets[ind]
									if not stored:
													__a :						int			       =  _Item(_lowercase	,			_lowercase     )
													self._len += 1
													return True
									elif stored.key == key:
													__a :						Tuple			       =  _Item(_lowercase	,			_lowercase     )
													return True
									else:
													return False







					def  _lowerCamelCase		(						self     ):
									__a :						Tuple			       =  len(self._buckets     ) * self._capacity_factor
									return len(self     ) >= int(_lowercase     )







					def  _lowerCamelCase		(						self     ):
									if len(self._buckets     ) <= self._initial_block_size:
													return False
									__a :						Optional[int]			       =  len(self._buckets     ) * self._capacity_factor / 2
									return len(self     ) < limit







					def  _lowerCamelCase		(						self	,			_UpperCAmelCase     ):
									__a :						int			       =  self._buckets
									__a :						Dict			       =  [None] * new_size
									__a :						str			       =  0
									for item in old_buckets:
													if item:
																	self._add_item(item.key	,			item.val     )







					def  _lowerCamelCase		(						self     ):
									self._resize(len(self._buckets     ) * 2     )







					def  _lowerCamelCase		(						self     ):
									self._resize(len(self._buckets     ) // 2     )







					def  _lowerCamelCase		(						self	,			_UpperCAmelCase     ):
									__a :						int			       =  self._get_bucket_index(_lowercase     )
									for _ in range(len(self._buckets     )     ):
													yield ind
													__a :						Tuple			       =  self._get_next_ind(_lowercase     )







					def  _lowerCamelCase		(						self	,			_UpperCAmelCase	,			_UpperCAmelCase     ):
									for ind in self._iterate_buckets(_lowercase     ):
													if self._try_set(_lowercase	,			_lowercase	,			_lowercase     ):
																	break







					def __setitem__(						self	,			_UpperCAmelCase	,			_UpperCAmelCase     ):
									if self._is_full():
													self._size_up()

									self._add_item(_lowercase	,			_lowercase     )







					def __delitem__(						self	,			_UpperCAmelCase     ):
									for ind in self._iterate_buckets(_lowercase     ):
													__a :						Tuple			       =  self._buckets[ind]
													if item is None:
																	raise KeyError(_lowercase     )
													if item is _deleted:
																	continue
													if item.key == key:
																	__a :						str			       =  _deleted
																	self._len -= 1
																	break
									if self._is_sparse():
													self._size_down()







					def __getitem__(						self	,			_UpperCAmelCase     ):
									for ind in self._iterate_buckets(_lowercase     ):
													__a :						Optional[int]			       =  self._buckets[ind]
													if item is None:
																	break
													if item is _deleted:
																	continue
													if item.key == key:
																	return item.val
									raise KeyError(_lowercase     )







					def __len__(						self     ):
									return self._len







					def __iter__(						self     ):
									yield from (item.key for item in self._buckets if item)







					def __repr__(						self     ):
									__a :						List[str]			       =  ' ,'.join(
									    f"""{item.key}: {item.val}""" for item in self._buckets if item     )
									return f"""HashMap({val_string})"""






"""simple docstring"""






def     __A      (			a_						:int = 2_00)		->		int:
				__a :						int			       =  [1, 2, 5, 10, 20, 50, 1_00, 2_00]
				__a :						List[Any]			       =  [0] * (pence + 1)
				__a :						Tuple			       =  1  # base case: 1 way to make 0 pence

				for coin in coins:
								for i in range(a_   ,       pence + 1   ,       1):
												number_of_ways[i] += number_of_ways[i - coin]
				return number_of_ways[pence]


if __name__ == "__main__":
		assert solution(200) == 73_682