题目描述

小 Petya 喜欢数数。他想统计用 $k$ 种颜色给一块 $n \times m$ 的方格板（$n$ 行、$m$ 列）染色的方案数，要求染色方案满足如下性质：对任何一条沿网格线把板子分成两个非空部分的竖线，两部分中不同颜色的数量都相同。请帮 Petya 数出这些染色方案。

输入格式

第一行包含用空格隔开的整数 $n$、$m$ 和 $k$（$1 \le n, m \le 1000$，$1 \le k \le 10^6$），分别表示板子的竖直与水平尺寸以及颜色种数。

输出格式

输出问题的答案。由于答案可能非常大，对 $10^9+7$ 取模后输出。

2 2 1

1

2 2 2

8

3 2 2

40