<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:
        '''
        dp[i][j]: number of ways to express
            i: use first ith integers
            j: sum up to j
        dp[i+1][j] = dp[i][j] + dp[i][j-(i+1)^x]

        optimization:
            space
            the range: 
                if the num is more than the target n, then no need to calculate
        '''
        MOD = 10**9+7
        dp = [0]*(n+1)
        dp[0] = 1
        for i in range(n):
            bound = (i+1) ** x
            if bound>n:
                break
            for j in range(n, bound-1, -1):
                # if j-bound in range(n+1):
                dp[j] += dp[j-bound]
        return dp[-1] % MOD

        # for i in range(1, n + 1):
        #     bound = i ** x  
        #     if bound > n:  
        #         break
        #     for j in range(n, bound - 1, -1):
        #         dp[j] += dp[j - bound]  # 转移方程
        #         dp[j] %= MOD  # 防止溢出，取模操作

        # return dp[n]  # 返回凑出总和 n 的方案数

# MX_N, MX_X = 300, 5
# f = [[1] + [0] * MX_N for _ in range(MX_X)]
# for x in range(MX_X):
#     for i in count(1):
#         v = i ** (x + 1)
#         if v > MX_N: break
#         for s in range(MX_N, v - 1, -1):
#             f[x][s] += f[x][s - v]

# class Solution:
#     def numberOfWays(self, n: int, x: int) -> int:
#         return f[x - 1][n] % (10 ** 9 + 7)

278