Computing coefficients of $p(x)^n$ in time $O(n \log n)$

For homework I've to give an algorithm that computes the coefficients of the polynomial $p(x)^n$ in time $O(n\log n)$, where $p(x)$ is a polynomial of degree 7.

As an hint I'm told to consider first the case where $n$ is a power of 2.

My guess is that I should use FFT and somehow manipulate it with modulo operations (maybe using the fact that for even powers the unity roots of power $n$ are the same as for $n/2$, only twice) but I'm pretty clueless about this one.

Suppose $n = 2^k$ and for $0\leq i \leq k$, set $p_i(x) = p(x)^{2^i}$. We want to efficiently compute $p_k(x)$.

It is clear that for $0\leq i < k$, $p_{i+1}(x) = p_i(x)^2$. Using the Cooley-Tukey algorithm, knowing $p_i(x)$, we can compute $p_{i+1}(x)$ in time complexity $O(d_i\log d_i)$ where $d_i = \deg p_i = \deg p \times 2^i = 7\times 2^i$.

We can know compute $p_k(x)$ by successively computing $p_1, p_2, …, p_{k-1}$. The total time complexity will be:

$$O\left(\sum\limits_{i=0}^{k-1} i 2^i\right) = O(k2^k) = O(n\log n)$$

Now for the general case where $n$ is not a power of two, you can choose the intermediate polynomials you compute based on the binary decomposition of $n$, like in fast exponentiation.

StackExchange Computer Science Q#140222, answer score: 3