'''simple docstring'''





from typing import Any





def       lowerCAmelCase_							(   snake_case_			:					list   ,       snake_case_			:					list   ,       snake_case_			:					dict   ,       snake_case_			:					dict   ,       snake_case_			:					dict   ,       )       -> list:


     '''simple docstring'''




     _validation(
         snake_case_   ,       snake_case_   ,       snake_case_   ,       snake_case_   ,       snake_case_   ,       )
     # Creates data structures and fill initial step
     UpperCAmelCase_			       =  {}
     UpperCAmelCase_			       =  {}
     for state in states_space:
          UpperCAmelCase_			       =  observations_space[0]
          UpperCAmelCase_			       =  (
              initial_probabilities[state] * emission_probabilities[state][observation]
          )
          UpperCAmelCase_			       =  None

     # Fills the data structure with the probabilities of
     # different transitions and pointers to previous states
     for o in range(1   ,       len(snake_case_     )     ):
          UpperCAmelCase_			       =  observations_space[o]
          UpperCAmelCase_			       =  observations_space[o - 1]
          for state in states_space:
               # Calculates the argmax for probability function
               UpperCAmelCase_			       =  ""
               UpperCAmelCase_			       =  -1
               for k_state in states_space:
                    UpperCAmelCase_			       =  (
                        probabilities[(k_state, prior_observation)]
                        * transition_probabilities[k_state][state]
                        * emission_probabilities[state][observation]
                    )
                    if probability > max_probability:
                         UpperCAmelCase_			       =  probability
                         UpperCAmelCase_			       =  k_state

            # Update probabilities and pointers dicts
               UpperCAmelCase_			       =  (
                   probabilities[(arg_max, prior_observation)]
                   * transition_probabilities[arg_max][state]
                   * emission_probabilities[state][observation]
               )

               UpperCAmelCase_			       =  arg_max

    # The final observation
     UpperCAmelCase_			       =  observations_space[len(snake_case_     ) - 1]

     # argmax for given final observation
     UpperCAmelCase_			       =  ""
     UpperCAmelCase_			       =  -1
     for k_state in states_space:
          UpperCAmelCase_			       =  probabilities[(k_state, final_observation)]
          if probability > max_probability:
               UpperCAmelCase_			       =  probability
               UpperCAmelCase_			       =  k_state
     UpperCAmelCase_			       =  arg_max

     # Process pointers backwards
     UpperCAmelCase_			       =  last_state
     UpperCAmelCase_			       =  []
     for o in range(len(snake_case_     ) - 1   ,       -1   ,       -1     ):
          result.append(snake_case_     )
          UpperCAmelCase_			       =  pointers[previous, observations_space[o]]
     result.reverse()

     return result





def       lowerCAmelCase_							(   snake_case_			:					Any   ,       snake_case_			:					Any   ,       snake_case_			:					Any   ,       snake_case_			:					Any   ,       snake_case_			:					Any   ,       )       -> None:


     '''simple docstring'''




     _validate_not_empty(
         snake_case_   ,       snake_case_   ,       snake_case_   ,       snake_case_   ,       snake_case_   ,       )
     _validate_lists(snake_case_   ,       snake_case_     )
     _validate_dicts(
         snake_case_   ,       snake_case_   ,       snake_case_     )





def       lowerCAmelCase_							(   snake_case_			:					Any   ,       snake_case_			:					Any   ,       snake_case_			:					Any   ,       snake_case_			:					Any   ,       snake_case_			:					Any   ,       )       -> None:


     '''simple docstring'''




     if not all(
         [
             observations_space,
             states_space,
             initial_probabilities,
             transition_probabilities,
             emission_probabilities,
         ]     ):
          raise ValueError("There's an empty parameter"     )





def       lowerCAmelCase_							(   snake_case_			:					Any   ,       snake_case_			:					Any     )       -> None:


     '''simple docstring'''




     _validate_list(snake_case_   ,       "observations_space"     )
     _validate_list(snake_case_   ,       "states_space"     )





def       lowerCAmelCase_							(   snake_case_			:					Any   ,       snake_case_			:					str     )       -> None:


     '''simple docstring'''




     if not isinstance(_object   ,       snake_case_     ):
          UpperCAmelCase_			       =  f"""{var_name} must be a list"""
          raise ValueError(snake_case_     )
     else:
          for x in _object:
               if not isinstance(snake_case_   ,       snake_case_     ):
                    UpperCAmelCase_			       =  f"""{var_name} must be a list of strings"""
                    raise ValueError(snake_case_     )





def       lowerCAmelCase_							(   snake_case_			:					Any   ,       snake_case_			:					Any   ,       snake_case_			:					Any   ,       )       -> None:


     '''simple docstring'''




     _validate_dict(snake_case_   ,       "initial_probabilities"   ,       snake_case_     )
     _validate_nested_dict(snake_case_   ,       "transition_probabilities"     )
     _validate_nested_dict(snake_case_   ,       "emission_probabilities"     )





def       lowerCAmelCase_							(   snake_case_			:					Any   ,       snake_case_			:					str     )       -> None:


     '''simple docstring'''




     _validate_dict(_object   ,       snake_case_   ,       snake_case_     )
     for x in _object.values():
          _validate_dict(snake_case_   ,       snake_case_   ,       snake_case_   ,       snake_case_     )





def       lowerCAmelCase_							(   snake_case_			:					Any   ,       snake_case_			:					str   ,       snake_case_			:					type   ,       snake_case_			:					bool = False     )       -> None:


     '''simple docstring'''




     if not isinstance(_object   ,       snake_case_     ):
          UpperCAmelCase_			       =  f"""{var_name} must be a dict"""
          raise ValueError(snake_case_     )
     if not all(isinstance(snake_case_   ,       snake_case_     ) for x in _object     ):
          UpperCAmelCase_			       =  f"""{var_name} all keys must be strings"""
          raise ValueError(snake_case_     )
     if not all(isinstance(snake_case_   ,       snake_case_     ) for x in _object.values()     ):
          UpperCAmelCase_			       =  "nested dictionary " if nested else ""
          UpperCAmelCase_			       =  f"""{var_name} {nested_text}all values must be {value_type.__name__}"""
          raise ValueError(snake_case_     )


if __name__ == "__main__":
    from doctest import testmod

    testmod()









'''simple docstring'''



lowerCAmelCase_  :							List[Any]             =    [0, 2, 4, 6, 8]
lowerCAmelCase_  :							str             =    [1, 3, 5, 7, 9]
def        UpperCAmelCase (    A	:					int       ,		A	:					int       ,		A	:					list[int]       ,		A	:					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

														SCREAMING_SNAKE_CASE       :   List[Any]         =      0
														for digit in range(10					):
																					SCREAMING_SNAKE_CASE       :   Optional[Any]         =      digit
																					result += reversible_numbers(
																					    0       ,		(remainder + 2 * digit) // 10       ,		A       ,		A					)
														return result

							SCREAMING_SNAKE_CASE       :   List[str]         =      0
							for digita in range(10					):
														SCREAMING_SNAKE_CASE       :   int         =      digita

														if (remainder + digita) % 2 == 0:
																					SCREAMING_SNAKE_CASE       :   str         =      ODD_DIGITS
														else:
																					SCREAMING_SNAKE_CASE       :   List[str]         =      EVEN_DIGITS

														for digita in other_parity_digits:
																					SCREAMING_SNAKE_CASE       :   Union[str, Any]         =      digita
																					result += reversible_numbers(
																					    remaining_length - 2       ,		(remainder + digita + digita) // 10       ,		A       ,		A       ,		)
							return result
def        UpperCAmelCase (    A	:					int = 9					):
							SCREAMING_SNAKE_CASE       :   Union[str, Any]         =      0
							for length in range(1       ,		max_power + 1					):
														result += reversible_numbers(A       ,		0       ,		[0] * length       ,		A					)
							return result


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




