





'''simple docstring'''




def 	UpperCAmelCase_							(					__lowercase							:      Optional[int]       )		->       Tuple:


     '''simple docstring'''



     if not head:
          return True
     # split the list to two parts
     _UpperCAmelCase     							=   head.next, head
     while fast and fast.next:
          _UpperCAmelCase     							=   fast.next.next
          _UpperCAmelCase     							=   slow.next
     _UpperCAmelCase     							=   slow.next
     _UpperCAmelCase     							=   None  # Don't forget here! But forget still works!
     # reverse the second part
     _UpperCAmelCase     							=   None
     while second:
          _UpperCAmelCase     							=   second.next
          _UpperCAmelCase     							=   node
          _UpperCAmelCase     							=   second
          _UpperCAmelCase     							=   nxt
     # compare two parts
     # second part has the same or one less node
     while node:
          if node.val != head.val:
               return False
          _UpperCAmelCase     							=   node.next
          _UpperCAmelCase     							=   head.next
     return True
def 	UpperCAmelCase_							(					__lowercase							:      str       )		->       Dict:


     '''simple docstring'''



     if not head or not head.next:
          return True

     # 1. Get the midpoint (slow)
     _UpperCAmelCase     							=   head
     while fast and fast.next:
          _UpperCAmelCase     							=   fast.next.next, slow.next

     # 2. Push the second half into the stack
     _UpperCAmelCase     							=   [slow.val]
     while slow.next:
          _UpperCAmelCase     							=   slow.next
          stack.append(slow.val       )

     # 3. Comparison
     while stack:
          if stack.pop() != cur.val:
               return False
          _UpperCAmelCase     							=   cur.next

     return True






def 	UpperCAmelCase_							(					__lowercase							:      Any       )		->       int:


     '''simple docstring'''



     if not head or not head.next:
          return True
     _UpperCAmelCase     							=   {}
     _UpperCAmelCase     							=   0
     while head:
          if head.val in d:
               d[head.val].append(__SCREAMING_SNAKE_CASE       )
          else:
               _UpperCAmelCase     							=   [pos]
          _UpperCAmelCase     							=   head.next
          pos += 1
     _UpperCAmelCase     							=   pos - 1
     _UpperCAmelCase     							=   0
     for v in d.values():
          if len(__SCREAMING_SNAKE_CASE       ) % 2 != 0:
               middle += 1
          else:
               _UpperCAmelCase     							=   0
               for i in range(0			,     len(__SCREAMING_SNAKE_CASE       )       ):
                    if v[i] + v[len(__SCREAMING_SNAKE_CASE       ) - 1 - step] != checksum:
                         return False
                    step += 1
          if middle > 1:
               return False
     return True





"""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())

