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.


We organise the $m\cdot n$ factors of $(mn)!$ into $n$ blocks of size $m$
  \begin{align*}
  ((j-1)&m+1)((j-1)m+2)\cdots((j-1)m+m)\tag{1}\\
  &=((j-1)m+1)((j-1)m+2)\cdots(jm-1)(jm)\qquad 1\leq j \leq n \\
  \end{align*}
Since for $0\leq m \leq k$ 
  \begin{align*}
\binom{k}{m}&=\frac{k!}{m!(k-m)!}\\
&=\frac{(k-m+1)\cdot(k-m+2)\cdots(k-1)\cdot k}{m!}\in\mathbb{N}
\end{align*}
  the product of $m$ consecutive integers $\geq 1$ is divided by $m!$. From (1) we conclude that for $1\leq j\leq n$
  \begin{align*}
  j( m!)\left|((j-1)m+1)((j-1)m+2)\cdots(jm-1)(jm)\right.\tag{2}
  \end{align*}
  since $jm!=(jm)(m-1)!$ and $(m-1)!$ divides the product \begin{align*}
\prod_{k=1}^{n-1}(((j-1)m+k)\qquad\qquad 1\leq j \leq n
\end{align*}
   of the $m-1$ consecutive numbers $(j-1)m+k, (k=1,\ldots,m-1)$.

$$ $$

We conclude:
\begin{align*}
 n!(m!)^n&=\left(\prod_{j=1}^nj\right)\left(\prod_{j=1}^nm!\right)\\
 &=\prod_{j=1}^n(m-1)!(mj)\\
 &\left|\ \prod_{j=1}^n((j-1)m+1)((j-1)m+2)\cdots(jm-1)(jm)\right.\tag{3}\\
  &=(nm)!\\
  \end{align*}

Comment:


*

*In (3) we use the divisibility property (2)

