





"""simple docstring"""





from __future__ import annotations

from collections.abc import Callable
from typing import Generic, TypeVar

SCREAMING_SNAKE_CASE__ =       TypeVar("T")
SCREAMING_SNAKE_CASE__ =       TypeVar("U")

class 		lowercase ( Generic[T, U] ):





      def __init__(	self				,						lowercase				,						lowercase			)		->					Any:
            lowerCAmelCase  						=	key
            lowerCAmelCase  						=	val
            lowerCAmelCase  						=	0
            lowerCAmelCase  						=	None
            lowerCAmelCase  						=	None





      def __repr__(	self			)		->					str:
            return "Node: key: {}, val: {}, freq: {}, has next: {}, has prev: {}".format(
                self.key				,						self.val				,						self.freq				,						self.next is not None				,						self.prev is not None			)







class 		lowercase ( Generic[T, U] ):





      def __init__(	self			)		->					None:
            lowerCAmelCase  						=	DoubleLinkedListNode(lowercase				,						lowercase			)
            lowerCAmelCase  						=	DoubleLinkedListNode(lowercase				,						lowercase			)
            lowerCAmelCase						,		lowerCAmelCase  						=	self.rear, self.head





      def __repr__(	self			)		->					str:
            lowerCAmelCase  						=	["""DoubleLinkedList"""]
            lowerCAmelCase  						=	self.head
            while node.next is not None:
                  rep.append(str(lowercase			)			)
                  lowerCAmelCase  						=	node.next
            rep.append(str(self.rear			)			)
            return ",\n    ".join(lowercase			)





      def    _snake_case      (	self				,						lowercase			)		->					None:
            lowerCAmelCase  						=	self.rear.prev

            # All nodes other than self.head are guaranteed to have non-None previous
            assert previous is not None

            lowerCAmelCase  						=	node
            lowerCAmelCase  						=	previous
            lowerCAmelCase  						=	node
            lowerCAmelCase  						=	self.rear
            node.freq += 1
            self._position_node(lowercase			)





      def    _snake_case      (	self				,						lowercase			)		->					None:

            while node.prev is not None and node.prev.freq > node.freq:
                  # swap node with previous node
                  lowerCAmelCase  						=	node.prev

                  lowerCAmelCase  						=	previous_node.prev
                  lowerCAmelCase  						=	node.prev
                  lowerCAmelCase  						=	previous_node
                  lowerCAmelCase  						=	node





      def    _snake_case      (	self				,						lowercase			)		->					DoubleLinkedListNode[T, U] | None:

            if node.prev is None or node.next is None:
                  return None

            lowerCAmelCase  						=	node.next
            lowerCAmelCase  						=	node.prev
            lowerCAmelCase  						=	None
            lowerCAmelCase  						=	None
            return node







class 		lowercase ( Generic[T, U] ):
      _SCREAMING_SNAKE_CASE         =				{}





      def __init__(	self				,						lowercase			)		->					str:
            lowerCAmelCase  						=	DoubleLinkedList()
            lowerCAmelCase  						=	capacity
            lowerCAmelCase  						=	0
            lowerCAmelCase  						=	0
            lowerCAmelCase  						=	0
            lowerCAmelCase  						=	{}





      def __repr__(	self			)		->					str:
            return (
                f'CacheInfo(hits={self.hits}, misses={self.miss}, '
                f'capacity={self.capacity}, current_size={self.num_keys})'
            )





      def __contains__(	self				,						lowercase			)		->					bool:
            return key in self.cache





      def    _snake_case      (	self				,						lowercase			)		->					U | None:

            if key in self.cache:
                  self.hits += 1
                  lowerCAmelCase  						=	self.cache[key]
                  lowerCAmelCase  						=	self.list.remove(self.cache[key]			)
                  assert node == value_node

                  # node is guaranteed not None because it is in self.cache
                  assert node is not None
                  self.list.add(lowercase			)
                  return node.val
            self.miss += 1
            return None





      def    _snake_case      (	self				,						lowercase				,						lowercase			)		->					None:

            if key not in self.cache:
                  if self.num_keys >= self.capacity:
                        # delete first node when over capacity
                        lowerCAmelCase  						=	self.list.head.next

                        # guaranteed to have a non-None first node when num_keys > 0
                        # explain to type checker via assertions
                        assert first_node is not None
                        assert first_node.key is not None
                        assert self.list.remove(lowercase			) is not None
                        # first_node guaranteed to be in list

                        del self.cache[first_node.key]
                        self.num_keys -= 1
                  lowerCAmelCase  						=	DoubleLinkedListNode(lowercase				,						lowercase			)
                  self.list.add(self.cache[key]			)
                  self.num_keys += 1

            else:
                  lowerCAmelCase  						=	self.list.remove(self.cache[key]			)
                  assert node is not None  # node guaranteed to be in list
                  lowerCAmelCase  						=	value
                  self.list.add(lowercase			)





      @classmethod
      def    _snake_case      (	cls				,						lowercase = 128			)		->					Callable[[Callable[[T], U]], Callable[..., U]]:

            def cache_decorator_inner(lowercase			) -> Callable[..., U]:
                  def cache_decorator_wrapper(*lowercase			) -> U:
                        if func not in cls.decorator_function_to_instance_map:
                              lowerCAmelCase  						=	LFUCache(lowercase			)

                        lowerCAmelCase  						=	cls.decorator_function_to_instance_map[func].get(args[0]			)
                        if result is None:
                              lowerCAmelCase  						=	func(*lowercase			)
                              cls.decorator_function_to_instance_map[func].put(args[0]				,						lowercase			)
                        return result

                  def cache_info() -> LFUCache[T, U]:
                        return cls.decorator_function_to_instance_map[func]

                  setattr(lowercase				,						"""cache_info"""				,						lowercase			)  # noqa: B010

                  return cache_decorator_wrapper

            return cache_decorator_inner


if __name__ == "__main__":
       import doctest

       doctest.testmod()













"""simple docstring"""





def       UpperCAmelCase__							(  SCREAMING_SNAKE_CASE					:						int							,						SCREAMING_SNAKE_CASE					:						int      ):







      '''simple docstring'''




      lowerCAmelCase  						=	1.0
      for i in range(1							,						r + 1      ):
            ret *= (n + 1 - i) / i
      return round(SCREAMING_SNAKE_CASE      )


def       UpperCAmelCase__							(  SCREAMING_SNAKE_CASE					:						int      ):







      '''simple docstring'''




      return choose(8 + n							,						SCREAMING_SNAKE_CASE      ) + choose(9 + n							,						SCREAMING_SNAKE_CASE      ) - 10


def       UpperCAmelCase__							(  SCREAMING_SNAKE_CASE					:						int      ):







      '''simple docstring'''




      return sum(non_bouncy_exact(SCREAMING_SNAKE_CASE      ) for i in range(1							,						n + 1      )      )


def       UpperCAmelCase__							(  SCREAMING_SNAKE_CASE					:						int = 1_00      ):







      '''simple docstring'''




      return non_bouncy_upto(SCREAMING_SNAKE_CASE      )


if __name__ == "__main__":
       print(f'{solution() = }')






