"""simple docstring"""
from __future__ import annotations

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

lowercase__   			=      TypeVar('T')
lowercase__   			=      TypeVar('U')




class   __snake_case			(	Generic[T, U]							):



      def __init__(		self       ,     lowercase       ,     lowercase)      ->     Union[str, Any]:





        '''simple docstring'''





        a__:	Dict     				=      key
        a__:	int     				=      val
        a__:	int     				=      0
        a__:	DoubleLinkedListNode[T, U] | None     				=      None
        a__:	DoubleLinkedListNode[T, U] | None     				=      None



      def __repr__(		self)      ->     str:





        '''simple docstring'''





        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   __snake_case			(	Generic[T, U]							):



      def __init__(		self)      ->     None:





        '''simple docstring'''





        a__:	DoubleLinkedListNode[T, U]     				=      DoubleLinkedListNode(lowercase       ,     lowercase)
        a__:	DoubleLinkedListNode[T, U]     				=      DoubleLinkedListNode(lowercase       ,     lowercase)
        a__				,       a__:	str     				=      self.rear, self.head



      def __repr__(		self)      ->     str:





        '''simple docstring'''





        a__:	Optional[Any]     				=      ['DoubleLinkedList']
        a__:	List[Any]     				=      self.head
        while node.next is not None:
          rep.append(str(lowercase))
          a__:	Optional[int]     				=      node.next
        rep.append(str(self.rear))
        return ",\n    ".join(lowercase)



      def     lowerCamelCase_  (		self       ,     lowercase)      ->     None:





        '''simple docstring'''





        a__:	Optional[int]     				=      self.rear.prev

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

        a__:	List[str]     				=      node
        a__:	Dict     				=      previous
        a__:	str     				=      node
        a__:	Optional[int]     				=      self.rear
        node.freq += 1
        self._position_node(lowercase)



      def     lowerCamelCase_  (		self       ,     lowercase)      ->     None:





        '''simple docstring'''





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

          a__:	Optional[int]     				=      previous_node.prev
          a__:	Dict     				=      node.prev
          a__:	Optional[int]     				=      previous_node
          a__:	Optional[int]     				=      node



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





        '''simple docstring'''





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

        a__:	int     				=      node.next
        a__:	Tuple     				=      node.prev
        a__:	Dict     				=      None
        a__:	List[str]     				=      None
        return node







class   __snake_case			(	Generic[T, U]							):
      a__								=						{}



      def __init__(		self       ,     lowercase)      ->     int:





        '''simple docstring'''





        a__:	DoubleLinkedList[T, U]     				=      DoubleLinkedList()
        a__:	Any     				=      capacity
        a__:	Optional[Any]     				=      0
        a__:	Optional[int]     				=      0
        a__:	Tuple     				=      0
        a__:	dict[T, DoubleLinkedListNode[T, U]]     				=      {}



      def __repr__(		self)      ->     str:





        '''simple docstring'''





        return (
            f'CacheInfo(hits={self.hits}, misses={self.miss}, '
            f'capacity={self.capacity}, current_size={self.num_keys})'
        )



      def __contains__(		self       ,     lowercase)      ->     bool:





        '''simple docstring'''





        return key in self.cache



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





        '''simple docstring'''





        if key in self.cache:
          self.hits += 1
          a__:	DoubleLinkedListNode[T, U]     				=      self.cache[key]
          a__:	Union[str, Any]     				=      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     lowerCamelCase_  (		self       ,     lowercase       ,     lowercase)      ->     None:





        '''simple docstring'''





        if key not in self.cache:
          if self.num_keys >= self.capacity:
            # delete first node when over capacity
            a__:	Optional[Any]     				=      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
          a__:	Optional[Any]     				=      DoubleLinkedListNode(lowercase       ,     lowercase)
          self.list.add(self.cache[key])
          self.num_keys += 1

        else:
          a__:	Union[str, Any]     				=      self.list.remove(self.cache[key])
          assert node is not None  # node guaranteed to be in list
          a__:	int     				=      value
          self.list.add(lowercase)



      @classmethod
      def     lowerCamelCase_  (		cls       ,     lowercase = 1_28)      ->     Callable[[Callable[[T], U]], Callable[..., U]]:





        '''simple docstring'''





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

            a__:	Any     				=      cls.decorator_function_to_instance_map[func].get(args[0])
            if result is None:
              a__:	int     				=      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()





import timeit





class    __UpperCAmelCase	:



   def __init__(				self				:	Dict,						__A				:	Union[str, Any]		):
     if isinstance(__A,						__A		):  # Initializes a matrix identical to the one provided.
       UpperCAmelCase			:				str										=					arg
       UpperCAmelCase			:				Optional[Any]										=					len(__A		)
     else:  # Initializes a square matrix of the given size and set values to zero.
       UpperCAmelCase			:				List[str]										=					arg
       UpperCAmelCase			:				List[Any]										=					[[0 for _ in range(self.n		)] for _ in range(self.n		)]





   def __mul__(				self				:	Dict,						__A				:	List[Any]		):
     UpperCAmelCase			:				Dict										=					Matrix(self.n		)
     for i in range(self.n		):
       for j in range(self.n		):
         for k in range(self.n		):
           matrix.t[i][j] += self.t[i][k] * b.t[k][j]
     return matrix






def      a__	(						UpperCAmelCase				:     List[str]							,					UpperCAmelCase				:     List[Any]     )    ->		str:
  UpperCAmelCase			:				Tuple										=					Matrix([[1, 0], [0, 1]]     )
  while b > 0:
    if b & 1:
      matrix *= a
    a *= a
    b >>= 1
  return matrix

def      a__	(						UpperCAmelCase				:     Any							,					UpperCAmelCase				:     Dict							,					UpperCAmelCase				:     Dict     )    ->		str:
  # Trivial Cases
  if n == 1:
    return fa
  elif n == 2:
    return fa
  UpperCAmelCase			:				List[str]										=					Matrix([[1, 1], [1, 0]]     )
  UpperCAmelCase			:				Union[str, Any]										=					modular_exponentiation(UpperCAmelCase							,					n - 2     )
  return fa * matrix.t[0][0] + fa * matrix.t[0][1]

def      a__	(						UpperCAmelCase				:     Any							,					UpperCAmelCase				:     int							,					UpperCAmelCase				:     List[Any]     )    ->		Optional[Any]:
  # Trivial Cases
  if n == 1:
    return fa
  elif n == 2:
    return fa

  UpperCAmelCase			:				str										=					fa
  UpperCAmelCase			:				List[str]										=					fa
  n -= 2

  while n > 0:
    UpperCAmelCase					,		UpperCAmelCase			:				str										=					fn_a + fn_a, fn_a
    n -= 1

  return fn_a

def      a__	(						)    ->		Any:
  UpperCAmelCase			:				int										=					'''
from random import randint
from __main__ import fibonacci_with_matrix_exponentiation
'''
  UpperCAmelCase			:				Dict										=					'''fibonacci_with_matrix_exponentiation(randint(1,70000), 1, 1)'''
  UpperCAmelCase			:				Tuple										=					timeit.timeit(setup=UpperCAmelCase							,					stmt=UpperCAmelCase							,					number=100     )
  print('''With matrix exponentiation the average execution time is '''							,					exec_time / 100     )
  return exec_time

def      a__	(						)    ->		int:
  UpperCAmelCase			:				str										=					'''
from random import randint
from __main__ import simple_fibonacci
'''
  UpperCAmelCase			:				List[str]										=					'''simple_fibonacci(randint(1,70000), 1, 1)'''
  UpperCAmelCase			:				List[str]										=					timeit.timeit(setup=UpperCAmelCase							,					stmt=UpperCAmelCase							,					number=100     )
  print(
      '''Without matrix exponentiation the average execution time is '''							,					exec_time / 100     )
  return exec_time

def      a__	(						)    ->		List[str]:
  matrix_exponentiation_time()
  simple_fibonacci_time()


if __name__ == "__main__":
     main()





