I think we take polinomial $P(x)=(-1)^n\cdot (n!)^{m-1}(x-1)\cdot (x-2)\cdot ...\cdot (x-n)$. Maybe you meant $m^k$.

@bove They meant indeed $m^k$.

What is $k$?

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).$$