Saudi Arabian Mathematical Competitions, 2015

Remember that if $P_{0}(X), P_{1}(X), P_{2}(X), \ldots$ are monic polynomials with integer coefficients such that $\deg P_{k}(X) = k$ for all $k = 0, 1, 2, \ldots$, then any polynomial $P(X)$ with integer coefficients can be written in a unique way as
$$P(X) = a_{0} P_{0}(X) + a_{1} P_{1}(X) + \cdots + a_{n} P_{n}(X),$$
where $a_{0}, a_{1}, \ldots, a_{n}$ are integers and $a_{n} \neq 0$. This can be proved by induction on the degree of $P(X)$ using the Euclidean algorithm.

Therefore, let us write our polynomial as:
$$P(x) = a_{0} x(x-1)(x-2)(x-3) + a_{1} x(x-1)(x-2) + a_{2} x(x-1) + a_{3} x + a_{4}.$$
Since $0 \leq a_{4} = P(0) < 72$, there are $72$ possible choices for $a_{4}$.

For any choice of $a_{4}$, we have $-a_{4} \leq a_{3} = P(1) - a_{4} < 72 - a_{4}$. Hence, we also have $72$ possible choices for $a_{3}$.

For each choice of $a_{3}$ and $a_{4}$ we have
$$-\frac{2 a_{3} + a_{4}}{2} \leq a_{2} = \frac{P(2) - 2 a_{3} - a_{4}}{2} < \frac{72}{2} - \frac{2 a_{3} + a_{4}}{2}.$$
Hence, there are $36$ possible choices for $a_{2}$.

Keep doing that way, the total number of polynomials is
$$72 \times 72 \times (72 / 2) \times (72 / 6) \times (72 / 24) = 72 \times 72 \times 36 \times 12 \times 3 = 2592^{2}.$$