





'''simple docstring'''




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

lowercase__    :      List[str]						=    TypeVar('''KEY''')
lowercase__    :      int						=    TypeVar('''VAL''')


@dataclass(frozen=__snake_case					,		slots=__snake_case							)
class  SCREAMING_SNAKE_CASE    (Generic[KEY, VAL]							):
     lowerCAmelCase					=       42
     lowerCAmelCase					=       42




class  SCREAMING_SNAKE_CASE    (_Item							):


     def __init__(						self):

          '''simple docstring'''






          super().__init__(__SCREAMING_SNAKE_CASE						,	__SCREAMING_SNAKE_CASE)


     def __bool__(						self):

          '''simple docstring'''






          return False




lowercase__    :      Optional[int]						=    _DeletedItem()


class  SCREAMING_SNAKE_CASE    (MutableMapping[KEY, VAL]							):


     def __init__(						self						,	_UpperCAmelCase = 8						,	_UpperCAmelCase = 0.75):

          '''simple docstring'''






          __A						: Dict      =       initial_block_size
          __A						: Optional[Any]      =       [None] * initial_block_size
          assert 0.0 < capacity_factor < 1.0
          __A						: Union[str, Any]      =       capacity_factor
          __A						: Optional[Any]      =       0


     def 							SCREAMING_SNAKE_CASE  (						self						,	_UpperCAmelCase):

          '''simple docstring'''






          return hash(__SCREAMING_SNAKE_CASE) % len(self._buckets)


     def 							SCREAMING_SNAKE_CASE  (						self						,	_UpperCAmelCase):

          '''simple docstring'''






          return (ind + 1) % len(self._buckets)


     def 							SCREAMING_SNAKE_CASE  (						self						,	_UpperCAmelCase						,	_UpperCAmelCase						,	_UpperCAmelCase):

          '''simple docstring'''






          __A						: Tuple      =       self._buckets[ind]
          if not stored:
               __A						: Optional[Any]      =       _Item(__SCREAMING_SNAKE_CASE						,	__SCREAMING_SNAKE_CASE)
               self._len += 1
               return True
          elif stored.key == key:
               __A						: Optional[int]      =       _Item(__SCREAMING_SNAKE_CASE						,	__SCREAMING_SNAKE_CASE)
               return True
          else:
               return False


     def 							SCREAMING_SNAKE_CASE  (						self):

          '''simple docstring'''






          __A						: Tuple      =       len(self._buckets) * self._capacity_factor
          return len(self) >= int(__SCREAMING_SNAKE_CASE)


     def 							SCREAMING_SNAKE_CASE  (						self):

          '''simple docstring'''






          if len(self._buckets) <= self._initial_block_size:
               return False
          __A						: int      =       len(self._buckets) * self._capacity_factor / 2
          return len(self) < limit


     def 							SCREAMING_SNAKE_CASE  (						self						,	_UpperCAmelCase):

          '''simple docstring'''






          __A						: List[str]      =       self._buckets
          __A						: Dict      =       [None] * new_size
          __A						: Optional[Any]      =       0
          for item in old_buckets:
               if item:
                    self._add_item(item.key						,	item.val)


     def 							SCREAMING_SNAKE_CASE  (						self):

          '''simple docstring'''






          self._resize(len(self._buckets) * 2)


     def 							SCREAMING_SNAKE_CASE  (						self):

          '''simple docstring'''






          self._resize(len(self._buckets) // 2)


     def 							SCREAMING_SNAKE_CASE  (						self						,	_UpperCAmelCase):

          '''simple docstring'''






          __A						: List[Any]      =       self._get_bucket_index(__SCREAMING_SNAKE_CASE)
          for _ in range(len(self._buckets)):
               yield ind
               __A						: List[str]      =       self._get_next_ind(__SCREAMING_SNAKE_CASE)


     def 							SCREAMING_SNAKE_CASE  (						self						,	_UpperCAmelCase						,	_UpperCAmelCase):

          '''simple docstring'''






          for ind in self._iterate_buckets(__SCREAMING_SNAKE_CASE):
               if self._try_set(__SCREAMING_SNAKE_CASE						,	__SCREAMING_SNAKE_CASE						,	__SCREAMING_SNAKE_CASE):
                    break


     def __setitem__(						self						,	_UpperCAmelCase						,	_UpperCAmelCase):

          '''simple docstring'''






          if self._is_full():
               self._size_up()

          self._add_item(__SCREAMING_SNAKE_CASE						,	__SCREAMING_SNAKE_CASE)


     def __delitem__(						self						,	_UpperCAmelCase):

          '''simple docstring'''






          for ind in self._iterate_buckets(__SCREAMING_SNAKE_CASE):
               __A						: int      =       self._buckets[ind]
               if item is None:
                    raise KeyError(__SCREAMING_SNAKE_CASE)
               if item is _deleted:
                    continue
               if item.key == key:
                    __A						: Optional[int]      =       _deleted
                    self._len -= 1
                    break
          if self._is_sparse():
               self._size_down()


     def __getitem__(						self						,	_UpperCAmelCase):

          '''simple docstring'''






          for ind in self._iterate_buckets(__SCREAMING_SNAKE_CASE):
               __A						: Dict      =       self._buckets[ind]
               if item is None:
                    break
               if item is _deleted:
                    continue
               if item.key == key:
                    return item.val
          raise KeyError(__SCREAMING_SNAKE_CASE)


     def __len__(						self):

          '''simple docstring'''






          return self._len


     def __iter__(						self):

          '''simple docstring'''






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


     def __repr__(						self):

          '''simple docstring'''






          __A						: Optional[int]      =       ' ,'.join(
              F'{item.key}: {item.val}' for item in self._buckets if item)
          return F'HashMap({val_string})'







"""simple docstring"""





def      lowerCamelCase__       (							_lowerCamelCase       :		int		,				_lowerCamelCase       :		int )      ->				int:
  lowerCamelCase_         =						1  # To kept the Calculated Value
  # Since C(n, k) = C(n, n-k)
  if k > (n - k):
    lowerCamelCase_         =						n - k
  # Calculate C(n,k)
  for i in range(_lowerCamelCase ):
    result *= n - i
    result //= i + 1
  return result







def      lowerCamelCase__       (							_lowerCamelCase       :		int )      ->				int:
  return binomial_coefficient(2 * node_count		,				_lowerCamelCase ) // (node_count + 1)







def      lowerCamelCase__       (							_lowerCamelCase       :		int )      ->				int:
  if n < 0:
    raise ValueError('factorial() not defined for negative values' )
  lowerCamelCase_         =						1
  for i in range(1		,				n + 1 ):
    result *= i
  return result







def      lowerCamelCase__       (							_lowerCamelCase       :		int )      ->				int:
  return catalan_number(_lowerCamelCase ) * factorial(_lowerCamelCase )


if __name__ == "__main__":
  _SCREAMING_SNAKE_CASE					:				int					    =						int(input('''Enter the number of nodes: ''').strip() or 0)
  if node_count <= 0:
    raise ValueError('''We need some nodes to work with.''')
  print(
      F'''Given {node_count} nodes, there are {binary_tree_count(node_count)} '''
      F'''binary trees and {catalan_number(node_count)} binary search trees.'''
  )




