SP7486 BIO1 - Rooks

Aly 是三年级中非常聪明的学生之一，他解决了一个问题：「在一个 $N \times M$ 的国际象棋棋盘上，放置 $K$ 个车，使得这些车互相不攻击的方法有多少种？」（车是可以攻击同一行或同一列上其他棋子的国际象棋棋子）。但 Aly 只能在 $N \times M$ 不超过 10 的情况下解决这个问题。几天后，他的一个同学自称能够解决 $N \times M$ 达到 100 的情况。Aly 不断追问他的解法，最后得知他用程序计算了结果。于是，Aly 决定公开挑战他的同学。但为此，他也需要一个不仅能在 $N \times M$ 达到 100 的情况下解决问题，还能在 $N$ 和 $M$ 各自达到 1,000,000 的情况下解决问题的程序。由于 Aly 知道结果可能非常大，因此希望程序输出的方法数对 1,000,000,007 取模。

输入一行，包含三个整数 $N$、$M$ 和 $K$（$1 \le N, M \le 1,000,000$，$1 \le K \le N \times M$）。

输出一个整数，表示满足条件的方法数对 1,000,000,007 取模后的结果。 **本翻译由 AI 自动生成**