


'''simple docstring'''



A__						:   List[str]				=    [0, 2, 4, 6, 8]
A__						:   Union[str, Any]				=    [1, 3, 5, 7, 9]



def      UpperCAmelCase__   (      UpperCAmelCase_       :							int ,       UpperCAmelCase_       :							int ,       UpperCAmelCase_       :							list[int] ,       UpperCAmelCase_       :							int				)	->						int:
     if remaining_length == 0:
          if digits[0] == 0 or digits[-1] == 0:
               return 0

          for i in range(length // 2 - 1 ,       -1 ,       -1				):
               remainder += digits[i] + digits[length - i - 1]

               if remainder % 2 == 0:
                    return 0

               remainder //= 10

          return 1

     if remaining_length == 1:
          if remainder % 2 == 0:
               return 0

          __lowerCamelCase  :      Optional[Any]														=						0
          for digit in range(10				):
               __lowerCamelCase  :      Optional[int]														=						digit
               result += reversible_numbers(
                   0 ,       (remainder + 2 * digit) // 10 ,       UpperCAmelCase_ ,       UpperCAmelCase_				)
          return result

     __lowerCamelCase  :      Optional[int]														=						0
     for digita in range(10				):
          __lowerCamelCase  :      List[Any]														=						digita

          if (remainder + digita) % 2 == 0:
               __lowerCamelCase  :      int														=						ODD_DIGITS
          else:
               __lowerCamelCase  :      Union[str, Any]														=						EVEN_DIGITS

          for digita in other_parity_digits:
               __lowerCamelCase  :      Optional[int]														=						digita
               result += reversible_numbers(
                   remaining_length - 2 ,       (remainder + digita + digita) // 10 ,       UpperCAmelCase_ ,       UpperCAmelCase_ ,       )
     return result



def      UpperCAmelCase__   (      UpperCAmelCase_       :							int = 9				)	->						int:
     __lowerCamelCase  :      List[Any]														=						0
     for length in range(1 ,       max_power + 1				):
          result += reversible_numbers(UpperCAmelCase_ ,       0 ,       [0] * length ,       UpperCAmelCase_				)
     return result


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










'''simple docstring'''



A__						:   dict[tuple[int, int, int], int]				=    {}



def      UpperCAmelCase__   (      UpperCAmelCase_       :							int ,       UpperCAmelCase_       :							int ,       UpperCAmelCase_       :							int				)	->						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
     __lowerCamelCase  :      List[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
     __lowerCamelCase  :      Tuple														=						_calculate(days - 1 ,       UpperCAmelCase_ ,       late + 1				)

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

     # 3) if we are on time, this resets the "late" counter and keeps the
     # absent counter
     __lowerCamelCase  :      List[Any]														=						_calculate(days - 1 ,       UpperCAmelCase_ ,       0				)

     __lowerCamelCase  :      Optional[int]														=						state_late + state_absent + state_ontime

     __lowerCamelCase  :      Union[str, Any]														=						prizestrings
     return prizestrings



def      UpperCAmelCase__   (      UpperCAmelCase_       :							int = 30				)	->						int:
     return _calculate(UpperCAmelCase_ ,       absent=0 ,       late=0				)


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






