


from math import pow


def 		lowercase_  (     _UpperCamelCase       ,			_UpperCamelCase       ,			_UpperCamelCase       ,			_UpperCamelCase       ,			_UpperCamelCase       ,			):


			'''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

			__lowercase 					=   int(pow(_UpperCamelCase       ,			_UpperCamelCase  )  )
			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
						__lowercase					, __lowercase 					=   backtrack(
						    _UpperCamelCase       ,			_UpperCamelCase       ,			current_number + 1       ,			_UpperCamelCase       ,			_UpperCamelCase  )
						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.
						__lowercase					, __lowercase 					=   backtrack(
						    _UpperCamelCase       ,			_UpperCamelCase       ,			current_number + 1       ,			_UpperCamelCase       ,			_UpperCamelCase  )
			return current_sum, solutions_count


def 		lowercase_  (     _UpperCamelCase       ,			_UpperCamelCase  ):


			'''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(_UpperCamelCase       ,			_UpperCamelCase       ,			1       ,			0       ,			0  )[1]  # Return the solutions_count


if __name__ == "__main__":
	import doctest

	doctest.testmod()






from typing import TYPE_CHECKING

from ...utils import OptionalDependencyNotAvailable, _LazyModule, is_torch_available


a : List[str]		=				{
    '''configuration_table_transformer''': [
        '''TABLE_TRANSFORMER_PRETRAINED_CONFIG_ARCHIVE_MAP''',
        '''TableTransformerConfig''',
        '''TableTransformerOnnxConfig''',
    ]
}

try:
	if not is_torch_available():
		raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
	pass
else:
	a : Union[str, Any]		=				[
	    '''TABLE_TRANSFORMER_PRETRAINED_MODEL_ARCHIVE_LIST''',
	    '''TableTransformerForObjectDetection''',
	    '''TableTransformerModel''',
	    '''TableTransformerPreTrainedModel''',
	]


if TYPE_CHECKING:
	from .configuration_table_transformer import (
	    TABLE_TRANSFORMER_PRETRAINED_CONFIG_ARCHIVE_MAP,
	    TableTransformerConfig,
	    TableTransformerOnnxConfig,
	)

	try:
		if not is_torch_available():
			raise OptionalDependencyNotAvailable()
	except OptionalDependencyNotAvailable:
		pass
	else:
		from .modeling_table_transformer import (
		    TABLE_TRANSFORMER_PRETRAINED_MODEL_ARCHIVE_LIST,
		    TableTransformerForObjectDetection,
		    TableTransformerModel,
		    TableTransformerPreTrainedModel,
		)

else:
	import sys

	a : Any		=				_LazyModule(__name__, globals()['''__file__'''], _import_structure, module_spec=__spec__)


