You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

编织（$\texttt{knit}$）

【题目描述】

小 D 在学习编织。

小 D 要在一块布料上插一些针眼，这个布料可以看成 $n\times m$ 的网格，针眼可以插在每个网格上，要求每个针眼所在的行和列中至多一个其他针眼。

• 如果一个针眼同行同列没有其他针眼，那么这个针眼上可以插 $k$ 种不同的花。
• 如果一个针眼同一行或同一列有其他针眼，那么这两个针眼必须用线起来。

小 D 想知道他可以织出多少种不同的图案。

【输入格式】

从 $\texttt{knit.in}$ 中读入数据。

第一行三个整数 $n,m,k$。

【输出格式】

输出到 $\texttt{knit.out}$ 中。

一行一个整数表示答案对 $10^9+7$ 取模后的结果。

【样例 1 输入】

2 2 3

【样例 1 输出】

34

【样例 2 输入】

255 196 123456

【样例 2 输出】

104775646

【样例 3 输入】

3000 1840 1

【样例 3 输出】

871302229

【样例 4 输入】

2024 2035 6737151

【样例 4 输出】

948813923

【数据范围】

对于所有测试数据有：$1\le n,m\le 3000,1\le k<10^9+7$。