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

@cache
def power(a: int, b: int) -> int:
    if b == 0:
        return 1
    if b == 1:
        return a
    
    x = power(a, b//2)
    res = x*x
    if b & 1:
        res*= a
    return res

MOD = 10**9 + 7

class Solution:
    def waysToAdd(self, n: int) -> int:
        # returns # of ways to add a subsequence of [1...n] to get n
        
        @cache
        def solve(d: int, cap: int) -> int:
            if d == 0:
                return 1
            
            t = 0
            for b in range(cap, 0, -1):
                new_d = d - b
                new_cap = min(new_d, b - 1)
                t+= solve(new_d, new_cap)
                t%= MOD
            return t
        return solve(n, n)

    def numberOfWays(self, n: int, x: int) -> int:
        if x == 1:
            return self.waysToAdd(n)

        exponent = 1/x
        min_sufficient_b = lambda d : ceil(d**exponent)

        # determine min b where b^x > n
        #   cant do max b where b^x <= n because of float precision
        max_b = min_sufficient_b(n)

        # every combination of b's is from [1, max_b]

        @cache
        def solve(d: int, cap: int) -> int:
            # returns number of ways to achieve d given cap
            #   assume d >= 0 and cap > 0
            if d == 0:
                return 1
            
            t = 0
            for b in range(cap, 0, -1):
                p = power(b, x)
                new_d = d - p
                if new_d < 0:
                    continue

                if new_d == 0:
                    t+= 1
                else:
                    new_cap = min(b-1, min_sufficient_b(new_d))
                    if new_cap < 1:
                        continue
                    t+= solve(new_d, new_cap)
                t%= MOD
            return t
        return solve(n, max_b)

45768