$p = 2$ does not fulfill the requirement, but $p = 3$ does: $a = 7^3 - 3 - 16 = 324 = 18^2$.

We show that there are no other solutions. Let $p \ge 5$ be a prime number.

If $p \equiv 1 \pmod 4$, then $a \equiv 2 \pmod 4$, which shows that $a$ is not a perfect square.

If $p > 3$ is a prime of the form $4k + 3$, then, from Fermat's Little Theorem it follows that $7^p \equiv 7 \pmod p$, hence $a \equiv -9 \pmod p$, i.e. $p \mid a + 9$. If $a$ is a perfect square, then $p$ divides $a + 9 = b^2 + 3^2$ would lead to $p$ divides $b$ and $p$ divides 3, which is not possible.

In conclusion, the only solution to the problem is $p = 3$.