在 ICPCCamp 中，有一个 $n$ 行 $m$ 列的棋盘。 Bobo 在棋盘的 $k$ 个不同格子里放置了 $k$ 个可区分的皇后。共有 $t = \binom{n \times m}{k}$ 种不同的放置方案，其中 $$\binom{n}{k} = \frac{n(n - 1) \dots (n - k + 1)}{k(k - 1)(k - 2) \dots 1}$$ 若 $c_i$ 表示第 $i$ 种方案中至少被一个皇后攻击到的格子数量，求 $(c_1 + c_2 + \dots + c_t)$ 对 $(10^9 + 7)$ 取模的结果。 注意：皇后可以攻击到与她处于同一行、同一列以及同一对角线上的所有格子（包括她所在的格子）。

输入格式

3 个整数 $n, m, k$ ($1 \le n, m \le 10^9, 1 \le k \le \min\{n \times m, 8\}$)。

输出格式

一个整数，表示 $(c_1 + c_2 + \dots + c_t)$ 对 $(10^9 + 7)$ 取模的结果。

样例

样例输入 1

2 2 2

样例输出 1

24

样例输入 2

8 8 8

样例输出 2

723759469