Algorithms
Medium
2787
2882
Ways to Express an Integer as Sum of Powers
ways-to-express-an-integer-as-sum-of-powers
"""
Given two positive integers n and x.

Return the number of ways n can be expressed as the sum of the xth power of unique positive integers, in other words, the number of sets of unique integers [n1, n2, ..., nk] where n = n1x + n2x + ... + nkx.

Since the result can be very large, return it modulo 109 + 7.

For example, if n = 160 and x = 3, one way to express n is n = 23 + 33 + 53.

Example 1:

Input: n = 10, x = 2
Output: 1
Explanation: We can express n as the following: n = 32 + 12 = 10.
It can be shown that it is the only way to express 10 as the sum of the 2nd power of unique integers.

Example 2:

Input: n = 4, x = 1
Output: 2
Explanation: We can express n in the following ways:
- n = 41 = 4.
- n = 31 + 11 = 4.


Constraints:

 * 1 <= n <= 300
 * 1 <= x <= 5
"""
class Solution:
    def numberOfWays(self, n: int, x: int) -> int:
        
Given two positive integers n and x.

Return the number of ways n can be expressed as the sum of the xth power of unique positive integers, in other words, the number of sets of unique integers [n1, n2, ..., nk] where n = n1x + n2x + ... + nkx.

Since the result can be very large, return it modulo 109 + 7.

For example, if n = 160 and x = 3, one way to express n is n = 23 + 33 + 53.

Example 1:

Input: n = 10, x = 2
Output: 1
Explanation: We can express n as the following: n = 32 + 12 = 10.
It can be shown that it is the only way to express 10 as the sum of the 2nd power of unique integers.

Example 2:

Input: n = 4, x = 1
Output: 2
Explanation: We can express n in the following ways:
- n = 41 = 4.
- n = 31 + 11 = 4.


Constraints:

 * 1 <= n <= 300
 * 1 <= x <= 5


Please complete the code below to solve above prblem:
```python
class Solution:
    def numberOfWays(self, n: int, x: int) -> int:
        
```

my_solution = Solution()

test_input = { "n": 10, "x": 2 }
assert my_solution.numberOfWays(**test_input) == 1

test_input = { "n": 4, "x": 1 }
assert my_solution.numberOfWays(**test_input) == 2

test_input = { "n": 1, "x": 1 }
assert my_solution.numberOfWays(**test_input) == 1

test_input = { "n": 1, "x": 2 }
assert my_solution.numberOfWays(**test_input) == 1

test_input = { "n": 1, "x": 3 }
assert my_solution.numberOfWays(**test_input) == 1

test_input = { "n": 1, "x": 4 }
assert my_solution.numberOfWays(**test_input) == 1

test_input = { "n": 1, "x": 5 }
assert my_solution.numberOfWays(**test_input) == 1

test_input = { "n": 2, "x": 1 }
assert my_solution.numberOfWays(**test_input) == 1

test_input = { "n": 2, "x": 2 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 2, "x": 3 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 2, "x": 4 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 2, "x": 5 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 3, "x": 1 }
assert my_solution.numberOfWays(**test_input) == 2

test_input = { "n": 3, "x": 2 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 3, "x": 3 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 3, "x": 4 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 3, "x": 5 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 4, "x": 2 }
assert my_solution.numberOfWays(**test_input) == 1

test_input = { "n": 4, "x": 3 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 4, "x": 4 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 4, "x": 5 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 5, "x": 1 }
assert my_solution.numberOfWays(**test_input) == 3

test_input = { "n": 5, "x": 2 }
assert my_solution.numberOfWays(**test_input) == 1

test_input = { "n": 5, "x": 3 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 5, "x": 4 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 5, "x": 5 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 6, "x": 1 }
assert my_solution.numberOfWays(**test_input) == 4

test_input = { "n": 6, "x": 2 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 6, "x": 3 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 6, "x": 4 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 6, "x": 5 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 7, "x": 1 }
assert my_solution.numberOfWays(**test_input) == 5

test_input = { "n": 7, "x": 2 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 7, "x": 3 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 7, "x": 4 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 7, "x": 5 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 8, "x": 1 }
assert my_solution.numberOfWays(**test_input) == 6

test_input = { "n": 8, "x": 2 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 8, "x": 3 }
assert my_solution.numberOfWays(**test_input) == 1

test_input = { "n": 8, "x": 4 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 8, "x": 5 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 9, "x": 1 }
assert my_solution.numberOfWays(**test_input) == 8

test_input = { "n": 9, "x": 2 }
assert my_solution.numberOfWays(**test_input) == 1

test_input = { "n": 9, "x": 3 }
assert my_solution.numberOfWays(**test_input) == 1

test_input = { "n": 9, "x": 4 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 9, "x": 5 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 10, "x": 1 }
assert my_solution.numberOfWays(**test_input) == 10

test_input = { "n": 10, "x": 3 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 10, "x": 4 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 10, "x": 5 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 11, "x": 1 }
assert my_solution.numberOfWays(**test_input) == 12

test_input = { "n": 11, "x": 2 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 11, "x": 3 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 11, "x": 4 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 11, "x": 5 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 12, "x": 1 }
assert my_solution.numberOfWays(**test_input) == 15

test_input = { "n": 12, "x": 2 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 12, "x": 3 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 12, "x": 4 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 12, "x": 5 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 13, "x": 1 }
assert my_solution.numberOfWays(**test_input) == 18

test_input = { "n": 13, "x": 2 }
assert my_solution.numberOfWays(**test_input) == 1

test_input = { "n": 13, "x": 3 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 13, "x": 4 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 13, "x": 5 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 14, "x": 1 }
assert my_solution.numberOfWays(**test_input) == 22

test_input = { "n": 14, "x": 2 }
assert my_solution.numberOfWays(**test_input) == 1

test_input = { "n": 14, "x": 3 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 14, "x": 4 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 14, "x": 5 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 15, "x": 1 }
assert my_solution.numberOfWays(**test_input) == 27

test_input = { "n": 15, "x": 2 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 15, "x": 3 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 15, "x": 4 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 15, "x": 5 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 16, "x": 1 }
assert my_solution.numberOfWays(**test_input) == 32

test_input = { "n": 16, "x": 2 }
assert my_solution.numberOfWays(**test_input) == 1

test_input = { "n": 16, "x": 3 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 16, "x": 4 }
assert my_solution.numberOfWays(**test_input) == 1

test_input = { "n": 16, "x": 5 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 17, "x": 1 }
assert my_solution.numberOfWays(**test_input) == 38

test_input = { "n": 17, "x": 2 }
assert my_solution.numberOfWays(**test_input) == 1

test_input = { "n": 17, "x": 3 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 17, "x": 4 }
assert my_solution.numberOfWays(**test_input) == 1

test_input = { "n": 17, "x": 5 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 18, "x": 1 }
assert my_solution.numberOfWays(**test_input) == 46

test_input = { "n": 18, "x": 2 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 18, "x": 3 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 18, "x": 4 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 18, "x": 5 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 19, "x": 1 }
assert my_solution.numberOfWays(**test_input) == 54

test_input = { "n": 19, "x": 2 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 19, "x": 3 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 19, "x": 4 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 19, "x": 5 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 20, "x": 1 }
assert my_solution.numberOfWays(**test_input) == 64

test_input = { "n": 20, "x": 2 }
assert my_solution.numberOfWays(**test_input) == 1

test_input = { "n": 20, "x": 3 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 20, "x": 4 }
assert my_solution.numberOfWays(**test_input) == 0

test_input = { "n": 20, "x": 5 }
assert my_solution.numberOfWays(**test_input) == 0