The zero polynomial is obviously a valid solution. Let $p$ be a non-zero polynomial and write $p(x) = a_nx^n + a_{n-1}x^{n-1} + \dots + a_0$, where $a_n \ne 0$. The leading term on the left-hand side of the equality is equal to $a_n(a_nx^n)^n = a_n^{n+1}x^{n^2}$, and the leading term on the right-hand side is $x^2 \cdot a_nx^n = a_nx^{n+2}$. The degrees of the two terms must be equal, so $n^2 = n + 2$, or $(n-2)(n+1) = 0$. Since $n$ is a non-negative integer, we conclude that $n=2$. Hence, $p(x) = ax^2 + bx + c$, where $a \ne 0$. We have:
$$p(p(x)) = a^3 x^4 + 2a^2 bx^3 + (ab^2 + 2a^2 c + ab)x^2 + (2abc + b^2)x + (ac^2 + bc + c) \quad (1)$$
$$(x^2 + x + 1)p(x) = ax^4 + (b+a)x^3 + (c+b+a)x^2 + (c+b)x + c. \quad (2)$$

From the given equality we obtain the system of equations
$$\begin{align*} a^3 &= a, \\ 2a^2b &= b+a, \\ ab^2 + 2a^2c + ab &= c+b+a, \\ 2abc + b^2 &= c+b, \\ ac^2 + bc + c &= c. \end{align*}$$
Since $a \neq 0$, the first equation implies $a = 1$ or $a = -1$. If $a = 1$ the second equation becomes $2b = b + 1$, so $b = 1$. Inserting both into the third equation we find that $2c + 2 = c + 2$, so $c = 0$. It is easy to check that these three numbers also satisfy the final two equations. If $a = -1$, then the system has no solutions. There are two solutions to the problem, namely $p(x) = 0$ and $p(x) = x^2 + x$.