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

precalc = [1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 2, 0, 0, 0, 0, 2, 1, 0, 0, 0, 3, 1, 0, 0, 0, 4, 0, 0, 0, 0, 5, 0, 0, 0, 0, 6, 0, 1, 0, 0, 8, 1, 1, 0, 0, 10, 1, 0, 0, 0, 12, 0, 0, 0, 0, 15, 0, 0, 0, 0, 18, 1, 0, 0, 0, 22, 1, 0, 0, 0, 27, 0, 0, 0, 0, 32, 1, 0, 1, 0, 38, 1, 0, 1, 0, 46, 0, 0, 0, 0, 54, 0, 0, 0, 0, 64, 1, 0, 0, 0, 76, 1, 0, 0, 0, 89, 0, 0, 0, 0, 104, 0, 0, 0, 0, 122, 0, 0, 0, 0, 142, 2, 0, 0, 0, 165, 2, 0, 0, 0, 192, 0, 1, 0, 0, 222, 0, 1, 0, 0, 256, 2, 0, 0, 0, 296, 2, 0, 0, 0, 340, 0, 0, 0, 0, 390, 0, 0, 0, 1, 448, 0, 0, 0, 1, 512, 1, 0, 0, 0, 585, 1, 1, 0, 0, 668, 1, 1, 0, 0, 760, 1, 0, 0, 0, 864, 1, 0, 0, 0, 982, 1, 0, 0, 0, 1113, 1, 0, 0, 0, 1260, 2, 0, 0, 0, 1426, 1, 0, 0, 0, 1610, 0, 0, 0, 0, 1816, 0, 0, 0, 0, 2048, 2, 0, 0, 0, 2304, 2, 0, 0, 0, 2590, 0, 0, 0, 0, 2910, 0, 0, 0, 0, 3264, 2, 0, 0, 0, 3658, 3, 0, 0, 0, 4097, 1, 0, 0, 0, 4582, 1, 0, 0, 0, 5120, 2, 0, 0, 0, 5718, 2, 0, 0, 0, 6378, 1, 0, 0, 0, 7108, 1, 0, 0, 0, 7917, 1, 0, 0, 0, 8808, 1, 0, 0, 0, 9792, 1, 0, 0, 0, 10880, 0, 0, 0, 0, 12076, 2, 0, 0, 0, 13394, 3, 0, 0, 0, 14848, 1, 0, 0, 0, 16444, 1, 1, 0, 0, 18200, 4, 1, 0, 0, 20132, 3, 0, 0, 0, 22250, 0, 0, 0, 0, 24576, 1, 0, 0, 0, 27130, 2, 0, 0, 0, 29927, 2, 0, 0, 0, 32992, 1, 0, 0, 0, 36352, 0, 1, 0, 0, 40026, 1, 1, 0, 0, 44046, 4, 0, 0, 0, 48446, 3, 0, 0, 0, 53250, 0, 0, 0, 0, 58499, 2, 0, 0, 0, 64234, 4, 0, 0, 0, 70488, 2, 0, 0, 0, 77312, 1, 0, 0, 0, 84756, 3, 0, 1, 0, 92864, 2, 0, 1, 0, 101698, 1, 0, 0, 0, 111322, 2, 0, 0, 0, 121792, 3, 0, 0, 0, 133184, 3, 0, 0, 0, 145578, 2, 0, 0, 0, 159046, 1, 0, 0, 0, 173682, 3, 0, 0, 0, 189586, 6, 0, 0, 0, 206848, 3, 1, 0, 0, 225585, 0, 1, 0, 0, 245920, 2, 0, 0, 0, 267968, 5, 0, 0, 0, 291874, 3, 0, 0, 0, 317788, 0, 0, 0, 0, 345856, 1, 0, 1, 0, 376256, 3, 0, 1, 0, 409174, 3, 1, 0, 0, 444793, 3, 1, 0, 0, 483330, 4, 0, 0, 0, 525016, 3, 0, 0, 0, 570078, 2, 0, 0, 0, 618784, 3, 0, 0, 0, 671418, 4, 0, 0, 0, 728260, 4, 0, 0, 0, 789640, 2, 0, 0, 0, 855906, 0, 0, 0, 0, 927406, 3, 0, 0, 0, 1004544, 7, 0, 0, 0, 1087744, 4, 0, 0, 0, 1177438, 0, 0, 0, 0, 1274118, 3, 0, 0, 0, 1378304, 6, 0, 0, 0, 1490528, 4, 0, 0, 0, 1611388, 3, 0, 0, 0, 1741521, 4, 0, 0, 0, 1881578, 3, 0, 0, 0, 2032290, 3, 0, 0, 0, 2194432, 4, 0, 0, 0, 2368800, 4, 0, 0, 0, 2556284, 4, 0, 0, 0, 2757826, 3, 0, 0, 0, 2974400, 1, 0, 0, 0, 3207086, 5, 1, 0, 0, 3457027, 9, 1, 0, 0, 3725410, 4, 0, 0, 0, 4013544, 0, 0, 0, 0, 4322816, 5, 0, 0, 0, 4654670, 9, 0, 0, 0, 5010688, 5, 0, 0, 0, 5392550, 1, 0, 0, 0, 5802008, 2, 1, 0, 0, 6240974, 6, 1, 0, 0, 6711480, 6, 0, 0, 0, 7215644, 3, 0, 0, 0, 7755776, 3, 0, 0, 0, 8334326, 6, 0, 0, 0, 8953856, 6, 0, 0, 0, 9617150, 3, 0, 0, 0, 10327156, 4, 0, 0, 0, 11086968, 7, 0, 0, 0, 11899934, 5, 0, 0, 0, 12769602, 2, 0, 0, 0, 13699699, 5, 0, 0, 0, 14694244, 9, 0, 0, 0, 15757502, 6, 0, 0, 0, 16893952, 2, 0, 0, 0, 18108418, 5, 0, 0, 0, 19406016, 9, 0, 0, 0, 20792120, 7, 0, 0, 0, 22272512, 3, 1, 0, 0, 23853318, 4, 1, 0, 0, 25540982, 7, 0, 0, 0, 27342421, 8, 0, 0, 0, 29264960, 5, 0, 0, 0, 31316314, 3, 0, 0, 0, 33504746, 7, 0, 0, 0, 35839008, 8, 0, 0, 0, 38328320, 4, 1, 0, 0, 40982540, 5, 1, 0, 0, 43812110, 8, 0, 0, 0, 46828032, 5, 0, 0, 0, 50042056, 4, 0, 0, 0, 53466624, 8, 0, 0, 0, 57114844, 8, 0, 0, 0, 61000704, 5, 0, 0, 0, 65139008, 4, 0, 0, 0, 69545358, 7, 0, 0, 0, 74236384, 11, 0, 0, 0, 79229676, 9, 0, 0, 0, 84543782, 3, 0, 0, 0, 90198446, 5, 0, 0, 0, 96214550, 13, 0, 0, 0, 102614114, 11, 0, 0, 0, 109420549, 3, 0, 0, 0, 116658616, 3, 0, 0, 0, 124354422, 9, 0, 0, 0, 132535702, 9, 0, 0, 0, 141231780, 6, 0, 0, 0, 150473568, 6, 0, 0, 0, 160293888, 8, 0, 0, 0, 170727424, 9, 0, 0, 0, 181810744, 7, 0, 0, 0, 193582642, 9, 0, 0, 0, 206084096, 12, 0, 0, 0, 219358315, 8, 0, 0, 0, 233451098, 2, 0, 0, 0, 248410816, 7, 1, 0, 0, 264288462, 14, 1, 0, 0, 281138048, 10, 0, 0, 0, 299016608, 3, 0, 0, 0, 317984256, 4, 0, 0, 0, 338104630, 14, 0, 0, 0, 359444904, 16, 0, 0, 0, 382075868, 8, 0, 0, 0, 406072422, 5, 1, 0, 0, 431513602, 11, 1, 0, 0, 458482688, 13, 0, 0, 0, 487067746, 9, 0, 0, 0, 517361670, 8, 0, 0, 0, 549462336, 8, 0, 0, 0, 583473184, 8, 0, 0, 0, 619503296, 7, 0, 0, 0, 657667584, 10, 0, 0, 0, 698087424, 14, 0, 0, 0, 740890786, 11, 0, 0, 0, 786212446, 6, 0, 0, 0, 834194700, 9, 0, 0, 0, 884987529, 18, 0, 0, 0, 938748852, 15, 0, 0, 0, 995645336, 6, 0, 0, 0, 55852583, 5, 0, 0, 0, 119555481, 12, 0, 0, 0, 186949049, 14, 0, 0, 0, 258238713, 8, 2, 0, 0, 333640703, 6, 2, 0, 0, 413383019, 10, 0, 0, 0, 497705761, 15, 0, 0, 0, 586861599, 11, 0, 0, 0, 681116845, 11, 0, 0, 0, 780751876, 16, 0, 0, 0, 886061677, 13, 0, 0, 0, 997357049, 7, 2, 0, 0, 114965106, 12, 2, 0, 0, 239229946, 17, 0, 0, 0, 370513972, 11, 0, 0, 0, 509198514, 6, 0, 0, 0, 655684594, 8, 0, 0, 0, 810394440, 17, 0, 0, 0, 973772198, 19, 0, 0, 0, 146284849, 10, 0, 0, 0, 328423915, 8, 0, 0, 0, 520706283, 20, 0, 0, 0, 723675305, 21, 0, 0, 0, 937902667, 9, 0, 0, 0, 163989430, 9, 0, 0, 0, 402567296, 17, 0, 0, 0, 654300678, 16, 0, 0, 0, 919887964, 8, 0, 0, 0, 200062941, 9, 0, 0, 0, 495597213, 15, 0, 0, 0, 807301597, 16, 1, 0, 1, 136027832, 12, 1, 0, 1, 482671280, 11, 0, 0, 0, 848172562, 19, 0, 0, 0, 233519570, 20, 0, 0, 0, 639750473, 12, 0, 0, 0, 67955656, 10, 0, 0, 0, 519280072, 21, 0, 0, 0, 994926546, 20, 1, 0, 0, 496158145, 8, 1, 0, 0, 24300820, 8, 0, 0, 0, 580747194, 19, 0, 0, 0, 166959261, 23, 0, 0, 0, 784471471, 13, 0, 1, 0, 434894980, 10, 0, 1, 0, 119920837, 18, 0, 0, 0, 841323491, 25, 0, 0, 0, 600965607, 19, 0, 0, 0, 400801751, 14, 0, 0, 0, 242882448, 15, 0, 0, 0, 129359625, 18, 0, 0, 0, 62490848, 17, 0, 0, 0, 44644013, 13, 0, 0, 0, 78303480, 17, 0, 0, 0, 166074989, 18, 0, 0, 0, 310691038, 12, 0, 0, 0, 515017823, 14, 0, 0, 0, 782060902, 28, 0, 0, 0, 114971358, 25, 0, 0, 0, 517053693, 11, 0, 1, 0, 991772290, 14, 0, 1, 0, 542758528, 26, 0, 0, 0, 173819680, 27, 0, 0, 1, 888946369, 16, 0, 0, 1, 692320715, 11, 0, 0, 0, 588326383, 16, 0, 0, 0, 581557167, 25, 0, 0, 0, 676826337, 21, 1, 0, 0, 879177939, 14, 1, 0, 0, 193896710, 20, 0, 0, 0, 626518758, 24, 0, 0, 0, 182844315, 17, 0, 0, 0, 868949151, 18, 0, 0, 0, 691196692, 31, 0, 0, 0, 656252574, 23, 0, 0, 0, 771097590, 9, 1, 0, 0, 43041626, 16, 1, 0, 0, 479740071, 31, 0, 0, 0, 89208609, 28, 0, 0, 0, 879839212, 13, 0, 0, 0, 860418576, 11, 0, 0, 0, 40145155, 25, 0, 0, 0, 428647317, 36, 0, 0, 0, 36004210, 24, 0, 0, 0, 872765252, 12, 0, 0, 0, 949970735, 21, 0, 0, 0, 279175535, 33, 0, 0, 0, 872471266, 25, 0, 0, 0]

class Solution:
    def numberOfWays(self, n: int, x: int) -> int:
        return precalc[(n - 1) * 5 + x - 1]
62