from math import pow







def     _a				(      lowercase__  :			int     ,  lowercase__  :			int     ,  lowercase__  :			int     ,  lowercase__  :			int     ,  lowercase__  :			int     ,  ):







					'''simple docstring'''


					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

					SCREAMING_SNAKE_CASE__				:				Union[str, Any]			=		int(pow(lowercase__     ,  lowercase__ ) )
					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
										SCREAMING_SNAKE_CASE__				:				List[str]			=		backtrack(
										    lowercase__     ,  lowercase__     ,  current_number + 1     ,  lowercase__     ,  lowercase__ )
										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.
										SCREAMING_SNAKE_CASE__				:				Optional[int]			=		backtrack(
										    lowercase__     ,  lowercase__     ,  current_number + 1     ,  lowercase__     ,  lowercase__ )
					return current_sum, solutions_count







def     _a				(      lowercase__  :			int     ,  lowercase__  :			int ):







					'''simple docstring'''


					if not (1 <= needed_sum <= 10_00 and 2 <= power <= 10):
										raise ValueError(
										    'Invalid input\n'
										    'needed_sum must be between 1 and 1000, power between 2 and 10.' )

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


if __name__ == "__main__":
						import doctest

						doctest.testmod()




def     _a				(      lowercase__  :			Optional[int] ):







     '''simple docstring'''


     SCREAMING_SNAKE_CASE__				:				Optional[int]			=		[]
     SCREAMING_SNAKE_CASE__				:				List[Any]			=		set({'(', '[', '{'} )
     SCREAMING_SNAKE_CASE__				:				Optional[int]			=		set({')', ']', '}'} )
     SCREAMING_SNAKE_CASE__				:				Union[str, Any]			=		{'{': '}', '[': ']', '(': ')'}

     for i in range(len(lowercase__ ) ):
          if s[i] in open_brackets:
               stack.append(s[i] )

          elif s[i] in closed_brackets and (
              len(lowercase__ ) == 0 or (len(lowercase__ ) > 0 and open_to_closed[stack.pop()] != s[i])
          ):
               return False

     return len(lowercase__ ) == 0







def     _a				(      ):







     '''simple docstring'''


     SCREAMING_SNAKE_CASE__				:				Tuple			=		input('Enter sequence of brackets: ' )
     if is_balanced(lowercase__ ):
          print(lowercase__     ,  'is balanced' )
     else:
          print(lowercase__     ,  'is not balanced' )


if __name__ == "__main__":
      main()



