"""simple docstring"""







from collections.abc import Sequence
from queue import Queue







class        UpperCamelCase		:
   def __init__(			self     ,__UpperCamelCase     ,__UpperCamelCase     ,__UpperCamelCase     ,__UpperCamelCase=None     ,__UpperCamelCase=None			)	->      int:


        '''simple docstring'''


        lowercase_	:				Dict													=	start
        lowercase_	:				List[Any]													=	end
        lowercase_	:				int													=	val
        lowercase_	:				Dict													=	(start + end) // 2
        lowercase_	:				List[Any]													=	left
        lowercase_	:				List[str]													=	right







   def __repr__(			self			)	->      Tuple:


        '''simple docstring'''


        return f'''SegmentTreeNode(start={self.start}, end={self.end}, val={self.val})'''







class        UpperCamelCase		:
   def __init__(			self     ,__UpperCamelCase     ,__UpperCamelCase			)	->      Union[str, Any]:


        '''simple docstring'''


        lowercase_	:				List[Any]													=	collection
        lowercase_	:				str													=	function
        if self.collection:
             lowercase_	:				int													=	self._build_tree(0     ,len(__UpperCamelCase			) - 1			)
   def 			_UpperCAmelCase   (			self     ,__UpperCamelCase     ,__UpperCamelCase			)	->      Any:


        '''simple docstring'''


        self._update_tree(self.root     ,__UpperCamelCase     ,__UpperCamelCase			)
   def 			_UpperCAmelCase   (			self     ,__UpperCamelCase     ,__UpperCamelCase			)	->      List[str]:


        '''simple docstring'''


        return self._query_range(self.root     ,__UpperCamelCase     ,__UpperCamelCase			)
   def 			_UpperCAmelCase   (			self     ,__UpperCamelCase     ,__UpperCamelCase			)	->      Any:


        '''simple docstring'''


        if start == end:
             return SegmentTreeNode(__UpperCamelCase     ,__UpperCamelCase     ,self.collection[start]			)
        lowercase_	:				List[Any]													=	(start + end) // 2
        lowercase_	:				str													=	self._build_tree(__UpperCamelCase     ,__UpperCamelCase			)
        lowercase_	:				Dict													=	self._build_tree(mid + 1     ,__UpperCamelCase			)
        return SegmentTreeNode(__UpperCamelCase     ,__UpperCamelCase     ,self.fn(left.val     ,right.val			)     ,__UpperCamelCase     ,__UpperCamelCase			)
   def 			_UpperCAmelCase   (			self     ,__UpperCamelCase     ,__UpperCamelCase     ,__UpperCamelCase			)	->      Optional[Any]:


        '''simple docstring'''


        if node.start == i and node.end == i:
             lowercase_	:				Tuple													=	val
             return
        if i <= node.mid:
             self._update_tree(node.left     ,__UpperCamelCase     ,__UpperCamelCase			)
        else:
             self._update_tree(node.right     ,__UpperCamelCase     ,__UpperCamelCase			)
        lowercase_	:				List[str]													=	self.fn(node.left.val     ,node.right.val			)
   def 			_UpperCAmelCase   (			self     ,__UpperCamelCase     ,__UpperCamelCase     ,__UpperCamelCase			)	->      str:


        '''simple docstring'''


        if node.start == i and node.end == j:
             return node.val

        if i <= node.mid:
             if j <= node.mid:
                  # range in left child tree
                  return self._query_range(node.left     ,__UpperCamelCase     ,__UpperCamelCase			)
             else:
                  # range in left child tree and right child tree
                  return self.fn(
                      self._query_range(node.left     ,__UpperCamelCase     ,node.mid			)     ,self._query_range(node.right     ,node.mid + 1     ,__UpperCamelCase			)     ,)
        else:
             # range in right child tree
             return self._query_range(node.right     ,__UpperCamelCase     ,__UpperCamelCase			)







   def 			_UpperCAmelCase   (			self			)	->      int:


        '''simple docstring'''


        if self.root is not None:
             lowercase_	:				Optional[Any]													=	Queue()
             queue.put(self.root			)
             while not queue.empty():
                  lowercase_	:				Optional[Any]													=	queue.get()
                  yield node

                  if node.left is not None:
                       queue.put(node.left			)

                  if node.right is not None:
                       queue.put(node.right			)


if __name__ == "__main__":
       import operator

       for fn in [operator.add, max, min]:
              print("*" * 50)
              __SCREAMING_SNAKE_CASE    	=SegmentTree([2, 1, 5, 3, 4], fn)
              for node in arr.traverse():
                     print(node)
              print()

              arr.update(1, 5)
              for node in arr.traverse():
                     print(node)
              print()

              print(arr.query_range(3, 4))  # 7
              print(arr.query_range(2, 2))  # 5
              print(arr.query_range(1, 3))  # 13
              print()


"""simple docstring"""







__SCREAMING_SNAKE_CASE    	={}



def 			lowercase__(       __SCREAMING_SNAKE_CASE							:     int     ,			__SCREAMING_SNAKE_CASE							:     int     ,			__SCREAMING_SNAKE_CASE							:     int      ):

     # if we are absent twice, or late 3 consecutive days,
     # no further prize strings are possible
     if late == 3 or absent == 2:
          return 0

     # if we have no days left, and have not failed any other rules,
     # we have a prize string
     if days == 0:
          return 1

     # No easy solution, so now we need to do the recursive calculation

     # First, check if the combination is already in the cache, and
     # if yes, return the stored value from there since we already
     # know the number of possible prize strings from this point on
     lowercase_	:				Any													=	(days, absent, late)
     if key in cache:
          return cache[key]

     # now we calculate the three possible ways that can unfold from
     # this point on, depending on our attendance today

     # 1) if we are late (but not absent), the "absent" counter stays as
     # it is, but the "late" counter increases by one
     lowercase_	:				Optional[int]													=	_calculate(days - 1     ,			__SCREAMING_SNAKE_CASE     ,			late + 1      )

     # 2) if we are absent, the "absent" counter increases by 1, and the
     # "late" counter resets to 0
     lowercase_	:				Any													=	_calculate(days - 1     ,			absent + 1     ,			0      )

     # 3) if we are on time, this resets the "late" counter and keeps the
     # absent counter
     lowercase_	:				Dict													=	_calculate(days - 1     ,			__SCREAMING_SNAKE_CASE     ,			0      )

     lowercase_	:				str													=	state_late + state_absent + state_ontime

     lowercase_	:				Tuple													=	prizestrings
     return prizestrings



def 			lowercase__(       __SCREAMING_SNAKE_CASE							:     int = 30      ):
     return _calculate(__SCREAMING_SNAKE_CASE     ,			absent=0     ,			late=0      )


if __name__ == "__main__":
       print(solution())

