



'''simple docstring'''

from typing import Any






def 		_snake_case		( _SCREAMING_SNAKE_CASE					:						list							,		_SCREAMING_SNAKE_CASE					:						list							,		_SCREAMING_SNAKE_CASE					:						dict							,		_SCREAMING_SNAKE_CASE					:						dict							,		_SCREAMING_SNAKE_CASE					:						dict							,		)      ->						list:







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

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

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

			lowerCAmelCase   =     arg_max

    # The final observation
	lowerCAmelCase   =     observations_space[len(_SCREAMING_SNAKE_CASE							) - 1]

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

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

	return result






def 		_snake_case		( _SCREAMING_SNAKE_CASE					:						Any							,		_SCREAMING_SNAKE_CASE					:						Any							,		_SCREAMING_SNAKE_CASE					:						Any							,		_SCREAMING_SNAKE_CASE					:						Any							,		_SCREAMING_SNAKE_CASE					:						Any							,		)      ->						None:







	"""simple docstring"""
	_validate_not_empty(
	    _SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							,		)
	_validate_lists(_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							)
	_validate_dicts(
	    _SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							)






def 		_snake_case		( _SCREAMING_SNAKE_CASE					:						Any							,		_SCREAMING_SNAKE_CASE					:						Any							,		_SCREAMING_SNAKE_CASE					:						Any							,		_SCREAMING_SNAKE_CASE					:						Any							,		_SCREAMING_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 		_snake_case		( _SCREAMING_SNAKE_CASE					:						Any							,		_SCREAMING_SNAKE_CASE					:						Any							)      ->						None:







	"""simple docstring"""
	_validate_list(_SCREAMING_SNAKE_CASE							,		"""observations_space"""							)
	_validate_list(_SCREAMING_SNAKE_CASE							,		"""states_space"""							)






def 		_snake_case		( _SCREAMING_SNAKE_CASE					:						Any							,		_SCREAMING_SNAKE_CASE					:						str							)      ->						None:







	"""simple docstring"""
	if not isinstance(_object							,		_SCREAMING_SNAKE_CASE							):
		lowerCAmelCase   =     f'{var_name} must be a list'
		raise ValueError(_SCREAMING_SNAKE_CASE							)
	else:
		for x in _object:
			if not isinstance(_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							):
				lowerCAmelCase   =     f'{var_name} must be a list of strings'
				raise ValueError(_SCREAMING_SNAKE_CASE							)






def 		_snake_case		( _SCREAMING_SNAKE_CASE					:						Any							,		_SCREAMING_SNAKE_CASE					:						Any							,		_SCREAMING_SNAKE_CASE					:						Any							,		)      ->						None:







	"""simple docstring"""
	_validate_dict(_SCREAMING_SNAKE_CASE							,		"""initial_probabilities"""							,		_SCREAMING_SNAKE_CASE							)
	_validate_nested_dict(_SCREAMING_SNAKE_CASE							,		"""transition_probabilities"""							)
	_validate_nested_dict(_SCREAMING_SNAKE_CASE							,		"""emission_probabilities"""							)






def 		_snake_case		( _SCREAMING_SNAKE_CASE					:						Any							,		_SCREAMING_SNAKE_CASE					:						str							)      ->						None:







	"""simple docstring"""
	_validate_dict(_object							,		_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							)
	for x in _object.values():
		_validate_dict(_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							)






def 		_snake_case		( _SCREAMING_SNAKE_CASE					:						Any							,		_SCREAMING_SNAKE_CASE					:						str							,		_SCREAMING_SNAKE_CASE					:						type							,		_SCREAMING_SNAKE_CASE					:						bool = False							)      ->						None:







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


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

				testmod()




'''simple docstring'''

from __future__ import annotations






def 		_snake_case		( _SCREAMING_SNAKE_CASE					:						int | str							)      ->						bool:







	"""simple docstring"""
	lowerCAmelCase   =     str(_SCREAMING_SNAKE_CASE							)
	return n == n[::-1]






def 		_snake_case		( _SCREAMING_SNAKE_CASE					:						int = 1_000_000							)      ->						Dict:







	"""simple docstring"""
	lowerCAmelCase   =     0

	for i in range(1							,		_SCREAMING_SNAKE_CASE							):
		if is_palindrome(_SCREAMING_SNAKE_CASE							) and is_palindrome(bin(_SCREAMING_SNAKE_CASE							).split("""b"""							)[1]							):
			total += i
	return total


if __name__ == "__main__":
				print(solution(int(str(input().strip()))))