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

Taken from this answer: $$ \begin{align} \frac{(m(n+1))!}{(m!)^{n+1}(n+1)!} &=\frac{(mn)!}{(m!)^nn!}\frac{(mn+1)(mn+2)\cdots(mn+m)}{m!(n+1)}\\ &=\frac{(mn)!}{(m!)^nn!}\frac{(mn+1)(mn+2)\cdots(mn+m-1)}{(m-1)!}\\ &=\frac{(mn)!}{(m!)^nn!}\binom{m(n+1)-1}{m-1}\tag{1} \end{align} $$ Inductively, from $(1)$ we get the formula $$ \bbox[5px,border:2px solid #C0A000]{\frac{(mn)!}{(m!)^nn!}=\prod_{k=1}^n\binom{mk-1}{m-1}}\tag{2} $$

By the Lemma, $$ \begin{align} \binom{mk-1}{m-1} &=\frac{(mk-1)!}{(m-1)!(mk-m)!}\\ &\in\mathbb{N}\tag{3} \end{align} $$ Therefore, $(2)$ is a product of integers, and so, an integer.

Let $a,b$ be non-negative integers. Since ${b+a\choose a}=\frac{(b+a)!}{a!\;b!}$ is an integer, we know that $$a!\;|\;(b+1)\cdot\ldots\cdot(b+a)={b+a\choose a}\;/\;b! \tag{*}$$

Now we use induction on $n$ to solve the original problem.

For $n=0$, the statement is trivially true. Suppose it holds for $n-1$ where $n \ge 1$. Then we have

$$\begin{align} n! \cdot (m!)^n &= n\cdot m!\cdot\left((n-1)!\cdot(m!)^{n-1}\right)\\ &\stackrel{hyp.}|n\cdot m! * (mn - m)!\\ &=n\cdot m!\cdot(mn)!\;/\;\left((mn-m+1)\ldots(mn)\right)\\ &=(m-1)!\cdot(mn)!\;/\;\left((mn-m+1)\ldots(mn-1)\right)\\ &\stackrel{(*)}|(mn)! \end{align}$$

Using the Lemma, it can be seen that $\dbinom{m}{r}$ is a positive integer, since,

$\dbinom{m}{n} = \dfrac{(m)!}{n!(m-n)!}$

Now, for positive integers $r$ and $m$, consider, the quantity

$$\dfrac{1}{r} \dbinom{rm}{m}$$

Since $\displaystyle \dbinom{m}{r} = \dfrac{m}{r} \dbinom{m-1}{r-1}$,

$$\implies \dfrac{1}{r} \dbinom{rm}{m} = \dbinom{rm-1}{m-1} \tag{1}$$

Thus, by $(1)$,

$\displaystyle \dfrac{1}{r}\dbinom{rm}{m} \in \mathbb{N} $

Let $\displaystyle \text{P} = \prod_{r=1}^{n} \dfrac{1}{r} \dbinom{rm}{m}$

$\displaystyle = \prod_{r=1}^{n} \dfrac{(rm)!}{[(r-1)m!](m!)r}$

$\displaystyle = \dfrac{1}{n! (m!)^n} \prod_{r=1}^{n} \dfrac{(rm)!}{((r-1)m!)} \tag{*} $

Note that $(*)$ telescopes, thus,

$\displaystyle \text{P} = \dfrac{(mn)!}{(m!)^n n!}$

But, since $\text{P}$ is a product of positive integers, it is itself a positive integer.

$$\displaystyle \implies \dfrac{(mn)!}{(m!)^n n!} \in \mathbb{N} \qquad \square$$