What does it mean when a time complexity has another time complexity within it?
This is somewhat informal, and to figure out what it means, just parse it inside-out:


$f(n)$ is $O(1)$ means, as usual "$\exists c, n_0: f(n) \leq c$ whenever $n \geq n_0$".
$f(n)$ is $n^{O(1)}$ is meant to mean "$f(n)$ is of the form $n^{g(n)}$, where $g(n)$ is $O(1)$". 

Formally put, $\exists c, n_0: f(n) \leq n^c$ whenever $n \geq n_0$.
$f(n)$ is $O(2^k \cdot n^{O(1)})$ means "$\exists c, n_0: f(n) \leq c\cdot 2^k\cdot n^{g(n)}$, where $g(n)$ is $O(1)$".

Formally put, $\exists c_1, c_2, n_0: f(n) \leq c_1 \cdot 2^k\cdot n^{c_2}$ whenever $n &gt; n_0$.


Note that you cannot simply replace the internal $O(1)$ with any fixed constant. You know that a suitable constant does exist, but its value is left unspecified.