Condition of cube of prime dividing $\prod_{i = 0}^{n} ((n - i)^3 + 1)$ This is a question from a French high school maths competition that I participated in today:

Let $n$ be a positive integer. Let $p$ be a prime number such that 
  $$p^3 \text{ divides } (1^3 + 1)(2^3 + 1)\cdots\left((n-1)^3 + 1\right)(n^3 + 1).$$
  Show that $p \leq n + 1$.

I have approached it by writing each $(n - i)^3 + 1$ in $\prod_{i = 0}^{n}\left((n - i)^3 + 1\right)$ as $(n - i + 1)\left((n - i)^2 - (n - i) + 1\right)$, and then the product then becomes
$$\begin{aligned}
&\prod_{i = 0}^n (n - i + 1)\left((n - i)^2 - (n - i) + 1\right)\\
&= (n + 1)! \prod_{i = 0}^n \left((n - i)^2 - (n - i) + 1\right)
\end{aligned}$$
If for the sake of contradiction, $p \leq n + 1$ does not hold, then $p$ does not divide $(n + 1)!$ and hence $p^3$ divides $\prod_{i = 0}^n \left((n - i)^2 - (n - i) + 1\right)$. Sadly, I failed to find the contradiction.
My question is then: where is the contradiction? Is there a better approach?
 A: In fact, it holds that $p\leq n-1$ (the inequality becomes an equality if and only if $p=2$ and $n=3$).  Suppose on the contrary that $p\geq n$.  The case $p=n$ can be reduced to the case $p=n+1$ by noting that $p^3+1$ is not divisible by $p$, and so the factor $p^3+1$ is irrelevant.  We can now safely assume that $p>n$.  
As you say, we have
$$p^3\mid \prod_{k=0}^n\,(k^2-k+1)\,.$$
Observe the followings.  First, $p^2$ does not divide $k^2-k+1$ for any $$k\in\{0,1,2,\ldots,n\}\subseteq \{0,1,2,\ldots,p-1\}\,.$$  This is simply because
$$0<k^2-k+1\leq k^2\leq (p-1)^2<p^2\,.$$
Hence, if $p^3\mid \prod\limits_{k=0}^n\,(k^2-k+1)$, then there must exist three pairwise distinct values $$k_1,k_2,k_3\in\{0,1,2,\ldots,n\}\subseteq \{0,1,2,\ldots,p-1\}$$ such that the congruence $t^2-t+1\equiv0\pmod{p}$ has solutions $t=k_1$, $t=k_2$, and $t=k_3$.  However, since $\mathbb{Z}/p\mathbb{Z}$ is a field, any quadratic polynomial in $(\mathbb{Z}/p\mathbb{Z})[t]$ has at most two solutions modulo $p$, and this is a contradiction you are looking for.
A: It's easier to write the product as: 
$$p^3|\prod_{i=1}^n(i^2-i+1).$$ 
Now, if $p>n+1$, then $p^2 >(n+1)^2\geq i^2-i+1. $ This means that there must be $1<i<j<k\leq n$ such that $p$ divides each of the factors corresponding to these indices. From this it is easy to get a contradiction. If $$p|i^2-i+1,\,\, j^2-j+1 $$
then their difference is also divisible by $p:$
$$p|(i-j)(i+j-1).$$
This also implies $$p|i+j-1.$$
Now do the same for the remaining possibilities and get a contradiction.
