<p>Given two <strong>positive</strong> integers <code>n</code> and <code>x</code>.</p>

<p>Return <em>the number of ways </em><code>n</code><em> can be expressed as the sum of the </em><code>x<sup>th</sup></code><em> power of <strong>unique</strong> positive integers, in other words, the number of sets of unique integers </em><code>[n<sub>1</sub>, n<sub>2</sub>, ..., n<sub>k</sub>]</code><em> where </em><code>n = n<sub>1</sub><sup>x</sup> + n<sub>2</sub><sup>x</sup> + ... + n<sub>k</sub><sup>x</sup></code><em>.</em></p>

<p>Since the result can be very large, return it modulo <code>10<sup>9</sup> + 7</code>.</p>

<p>For example, if <code>n = 160</code> and <code>x = 3</code>, one way to express <code>n</code> is <code>n = 2<sup>3</sup> + 3<sup>3</sup> + 5<sup>3</sup></code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 10, x = 2
<strong>Output:</strong> 1
<strong>Explanation:</strong> We can express n as the following: n = 3<sup>2</sup> + 1<sup>2</sup> = 10.
It can be shown that it is the only way to express 10 as the sum of the 2<sup>nd</sup> power of unique integers.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 4, x = 1
<strong>Output:</strong> 2
<strong>Explanation:</strong> We can express n in the following ways:
- n = 4<sup>1</sup> = 4.
- n = 3<sup>1</sup> + 1<sup>1</sup> = 4.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 300</code></li>
	<li><code>1 &lt;= x &lt;= 5</code></li>
</ul>

class Solution:
    def numberOfWays(self, n: int, x: int) -> int:
        # https://github.com/doocs/leetcode/tree/main/solution/2700-2799/2787.Ways%20to%20Express%20an%20Integer%20as%20Sum%20of%20Powers
        mod = 10 ** 9 + 7      
        # Initializing a dynamic programming table where
        # dp[i][j] represents the number of ways to write j as a sum
        # of i-th powers of first i natural numbers.
        dp = [[0] * (n + 1) for _ in range(n + 1)]
      
        # There is one way to form the sum 0 using 0 numbers: use no numbers at all.
        dp[0][0] = 1
      
        # Iterate over all numbers from 1 to total_sum
        for i in range(1, n + 1):
            # Calculate the i-nth power of the number
            power = pow(i, x)
            # Iterate over all possible sums from 0 to total_sum
            for j in range(n + 1):
                # The number of ways to form the sum j without using the i-th number
                dp[i][j] = dp[i - 1][j]
                # If the power is less than or equal to the sum j, then
                # add the number of ways to form the previous sum j-power
                if power <= j:
                    dp[i][j] = (dp[i][j] + dp[i - 1][j - power]) % mod
      
        # Return the number of ways to write total_sum as a sum of
        # powers of the first total_sum natural numbers.
        return dp[n][n]


        # @cache
        # def backtrack(i, cur):
        #     if cur == n:                
        #         return 1            
        #     ans = 0
        #     for j in range(i, len(candidates)):  
        #         if cur + candidates[j] > n:
        #             break              
        #         ans += backtrack(j + 1, cur + candidates[j])
        #         ans = ans % (10 ** 9 + 7)
        #     return ans

        # candidates = []
        # i = 1
        # while i <= n:
        #     if i ** x <= n:
        #         candidates.append(i ** x)
        #         i += 1
        #     else:
        #         break
        # candidates.sort()
        # ans = backtrack(0, 0)
        # return ans % (10 ** 9 + 7)
2330