See a slightly stronger version here. (EDIT: checking the timestamp, it seems that I thought of this problem at around the same time as it was on the Balkan shortlist! How odd... In any case, as I indicate in the source field of the linked thread, this problem is not really new. I wonder how it got on the shortlist of a major international Olympiad though?)
Choose integers $k,C$ such that:
$\nu_p\left(m^k\right)>\nu_p(n!)$ for any prime $p\mid m$.
$\nu_p(C)>\nu_p(n!)$ for any prime $p\nmid m$.
Then this polynomial works: $$P(x)=m^k\sum_{r=0}^n\left(m^{\varphi(C)}-1\right)^r\cdot\binom{x}{r}.$$An alternative solution that works for this problem (but not for the one in the link, where we need the $P(i)$ to be distinct) is to choose $a,b$ such that $m^a\equiv m^b\pmod{n!}$. Then take $$P(x)=m^a+\left(\frac{m^b-m^a}{n!}\right)\cdot\prod_{r=0}^{n-1}(x-r).$$