CF111D.Petya and Coloring

Little Petya loves counting. He wants to count the number of ways to paint a rectangular checkered board of size n × m (n rows, m columns) in k colors. Besides, the coloring should have the following property: for any vertical line that passes along the grid lines and divides the board in two non-empty parts the number of distinct colors in both these parts should be the same. Help Petya to count these colorings.

小Petya热爱计数。他想计算将一个 $n \times m$（$n$ 行，$m$ 列）的矩形方格棋盘用 $k$ 种颜色进行染色的方案数。此外，染色需满足如下性质：对任意一条沿网格线画出的竖直直线，若该直线将棋盘分成两个非空部分，则这两个部分中各自出现的不同颜色的种数必须相等。请帮助 Petya 计算满足条件的染色方案总数。

The first line contains space-separated integers n, m and k (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 106) — the board's vertical and horizontal sizes and the number of colors respectively.

第一行包含三个以空格分隔的整数 $n$、$m$ 和 $k$（$1 ≤ n, m ≤ 1000$，$1 ≤ k ≤ 10^6$），分别表示棋盘的垂直尺寸、水平尺寸以及颜色种类数。

Print the answer to the problem. As the answer can be quite a large number, you should print it modulo 109 + 7 (1000000007).

输出该问题的答案。由于答案可能非常大，因此你需要输出其对 $10^9 + 7$（即 $1000000007$）取模的结果。