




"""simple docstring"""





from math import pow
def      a__			(   lowerCAmelCase__			,    lowerCAmelCase__			,    lowerCAmelCase__			,    lowerCAmelCase__			,    lowerCAmelCase__			,    ):
      if current_sum == needed_sum:
            # If the sum of the powers is equal to needed_sum, then we have a solution.
            solutions_count += 1
            return current_sum, solutions_count

      UpperCAmelCase_    				=							int(pow(lowerCAmelCase__			,    lowerCAmelCase__   )   )
      if current_sum + i_to_n <= needed_sum:
            # If the sum of the powers is less than needed_sum, then continue adding powers.
            current_sum += i_to_n
            UpperCAmelCase_				,					UpperCAmelCase_    				=							backtrack(
                lowerCAmelCase__			,    lowerCAmelCase__			,    current_number + 1			,    lowerCAmelCase__			,    lowerCAmelCase__   )
            current_sum -= i_to_n
      if i_to_n < needed_sum:
            # If the power of i is less than needed_sum, then try with the next power.
            UpperCAmelCase_				,					UpperCAmelCase_    				=							backtrack(
                lowerCAmelCase__			,    lowerCAmelCase__			,    current_number + 1			,    lowerCAmelCase__			,    lowerCAmelCase__   )
      return current_sum, solutions_count
def      a__			(   lowerCAmelCase__			,    lowerCAmelCase__   ):
      if not (1 <= needed_sum <= 1000 and 2 <= power <= 10):
            raise ValueError(
                "Invalid input\n"
                "needed_sum must be between 1 and 1000, power between 2 and 10."   )

      return backtrack(lowerCAmelCase__			,    lowerCAmelCase__			,    1			,    0			,    0   )[1]  # Return the solutions_count


if __name__ == "__main__":
  import doctest

  doctest.testmod()









"""simple docstring"""





from __future__ import annotations
def      a__			(   lowerCAmelCase__			,    lowerCAmelCase__			,    lowerCAmelCase__			,    lowerCAmelCase__   ):
      UpperCAmelCase_    				=							[]
      UpperCAmelCase_				,					UpperCAmelCase_    				=							input_list[low:mid], input_list[mid : high + 1]
      while left and right:
            result.append((left if left[0] <= right[0] else right).pop(0   )   )
      UpperCAmelCase_    				=							result + left + right
      return input_list
def      a__			(   lowerCAmelCase__   ):
      if len(lowerCAmelCase__   ) <= 1:
            return input_list
      UpperCAmelCase_    				=							list(lowerCAmelCase__   )

      # iteration for two-way merging
      UpperCAmelCase_    				=							2
      while p <= len(lowerCAmelCase__   ):
            # getting low, high and middle value for merge-sort of single list
            for i in range(0			,    len(lowerCAmelCase__   )			,    lowerCAmelCase__   ):
                  UpperCAmelCase_    				=							i
                  UpperCAmelCase_    				=							i + p - 1
                  UpperCAmelCase_    				=							(low + high + 1) // 2
                  UpperCAmelCase_    				=							merge(lowerCAmelCase__			,    lowerCAmelCase__			,    lowerCAmelCase__			,    lowerCAmelCase__   )
            # final merge of last two parts
            if p * 2 >= len(lowerCAmelCase__   ):
                  UpperCAmelCase_    				=							i
                  UpperCAmelCase_    				=							merge(lowerCAmelCase__			,    0			,    lowerCAmelCase__			,    len(lowerCAmelCase__   ) - 1   )
                  break
            p *= 2

      return input_list


if __name__ == "__main__":
  lowerCamelCase      =		input("""Enter numbers separated by a comma:\n""").strip()
  if user_input == "":
    lowerCamelCase      =		[]
  else:
    lowerCamelCase      =		[int(item.strip()) for item in user_input.split(""",""")]
  print(iter_merge_sort(unsorted))




