





'''simple docstring'''


from __future__ import annotations

from collections import deque
from collections.abc import Iterator
from dataclasses import dataclass






@dataclass
class     lowerCAmelCase__ :

       '''simple docstring'''
       _lowerCamelCase								=42
       _lowerCamelCase								=42






class     lowerCAmelCase__ :

       '''simple docstring'''

       def __init__( self					:				Union[str, Any]       ,     a__					:				int						):
              UpperCAmelCase  =						[[] for _ in range(a__						)]
              UpperCAmelCase  =						size

       def __getitem__( self					:				Any       ,     a__					:				int						):
              return iter(self._graph[vertex]						)

       @property
       def 			__snake_case      ( self					:				List[str]						):
              return self._size

       def 			__snake_case      ( self					:				Optional[Any]       ,     a__					:				int       ,     a__					:				int       ,     a__					:				int						):
              if weight not in (0, 1):
                     raise ValueError('''Edge weight must be either 0 or 1.'''						)

              if to_vertex < 0 or to_vertex >= self.size:
                     raise ValueError('''Vertex indexes must be in [0; size).'''						)

              self._graph[from_vertex].append(Edge(a__       ,     a__						)						)



       def 			__snake_case      ( self					:				Dict       ,     a__					:				int       ,     a__					:				int						):
              UpperCAmelCase  =						deque([start_vertex]						)
              UpperCAmelCase  =						[None] * self.size
              UpperCAmelCase  =						0

              while queue:
                     UpperCAmelCase  =						queue.popleft()
                     UpperCAmelCase  =						distances[current_vertex]
                     if current_distance is None:
                            continue

                     for edge in self[current_vertex]:
                            UpperCAmelCase  =						current_distance + edge.weight
                            UpperCAmelCase  =						distances[edge.destination_vertex]
                            if (
                                isinstance(a__       ,     a__						)
                                and new_distance >= dest_vertex_distance
                            ):
                                   continue
                            UpperCAmelCase  =						new_distance
                            if edge.weight == 0:
                                   queue.appendleft(edge.destination_vertex						)
                            else:
                                   queue.append(edge.destination_vertex						)

              if distances[finish_vertex] is None:
                     raise ValueError('''No path from start_vertex to finish_vertex.'''						)

              return distances[finish_vertex]


if __name__ == "__main__":
    import doctest

    doctest.testmod()







_lowercase    	=		[0, 2, 4, 6, 8]
_lowercase    	=		[1, 3, 5, 7, 9]



def 		lowerCAmelCase__     (       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 //= 1_0

        return 1

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

        A__					=       0
        for digit in range(1_0						):
            A__					=       digit
            result += reversible_numbers(
                0			,							(remainder + 2 * digit) // 1_0			,							UpperCamelCase_			,							UpperCamelCase_						)
        return result

    A__					=       0
    for digita in range(1_0						):
        A__					=       digita

        if (remainder + digita) % 2 == 0:
            A__					=       ODD_DIGITS
        else:
            A__					=       EVEN_DIGITS

        for digita in other_parity_digits:
            A__					=       digita
            result += reversible_numbers(
                remaining_length - 2			,							(remainder + digita + digita) // 1_0			,							UpperCamelCase_			,							UpperCamelCase_			,							)
    return result



def 		lowerCAmelCase__     (       UpperCamelCase_					:							int = 9						)->	int:
    A__					=       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() = }")
