Prove that $(mn)!$ is divisible by $(n!)\cdot(m!)^n$ 
Let $m$ be a positive integer and $n$ a nonnegative integer. Prove that
$$(n!)\cdot(m!)^n|(mn)!$$

I can prove it using Legendre's Formula, but I have to use the lemma that
$$ \dfrac{\displaystyle\left(\sum_{i=1}^na_i\right)!}{\displaystyle\prod_{i=1}^na_i!} \in \mathbb{N} $$
I believe that it can be proved using the lemma, since in this answer of Qiaochu Yuan he has mentioned so at the end of his answer.
Any help will be appreciated.
Thanks.

Consider you have $mn$ balls with $n$ different colors and $m$ balls of each color. The number of possible arrangements is $$(mn)!\over (m!)^n$$.
However each arrangement has $n!$ "symmetric arrangements", that is, if we exchange color between whole groups we obtain a symmetric arrangement. I.E. for example if we have three color R,G,B, then $RGRBGB$ and $GRGBRB$ are symmetric arrangement by exchanging colors $R$ and $G$.
Thus $(mn)!\over (m!)^n$ is a multiple of $n!$.
