



'''simple docstring'''






def        snake_case_   (	lowerCAmelCase_			,  lowerCAmelCase_						)->						Union[str, Any]:





       '''simple docstring'''


       if n < 0:
              return 0
       # table[i] represents the number of ways to get to amount i
       _UpperCAmelCase    :		Union[str, Any]     	=					[0] * (n + 1)

       # There is exactly 1 way to get to zero(You pick no coins).
       _UpperCAmelCase    :		Optional[int]     	=					1

       # Pick all coins one by one and update table[] values
       # after the index greater than or equal to the value of the
       # picked coin
       for coin_val in s:
              for j in range(lowerCAmelCase_			,  n + 1						):
                     table[j] += table[j - coin_val]

       return table[n]


if __name__ == "__main__":
   import doctest

   doctest.testmod()





"""simple docstring"""






import math






def 		_snake_case			(      lowercase__						:    int						)    ->							int:


			'''simple docstring'''





			return sum(int(lowercase__						) for digit in str(lowercase__						)						)






def 		_snake_case			(      lowercase__						:    int = 3_0						)    ->							int:


			'''simple docstring'''





			lowerCAmelCase_       :Union[str, Any]     	=    []
			for digit in range(2 ,	1_0_0						):
						for power in range(2 ,	1_0_0						):
									lowerCAmelCase_       :Tuple     	=    int(math.pow(lowercase__ ,	lowercase__						)						)
									if digit == digit_sum(lowercase__						):
												digit_to_powers.append(lowercase__						)

			digit_to_powers.sort()
			return digit_to_powers[n - 1]


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






