小彼佳喜欢数数。他想计算用 k 种颜色绘制大小为 n × m(n 行,m 列)的矩形方格板的方法数。此外,着色应具有以下属性:对于任何沿着网格线并将棋盘分为两个非空部分的垂直线,这两个部分中不同颜色的数量应该相同。帮助 Petya 数一下这些颜色。
输入
第一行包含空格分隔的整数 n、m 和 k (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 106) — 分别是棋盘的垂直和水平尺寸以及颜色数量。
输出
打印问题的答案。由于答案可能是一个相当大的数字,因此您应该打印它模 109 + 7 (1000000007)。
示例
输入 #1
2 2 1
输出 #1
1
输入 #2
2 2 2
输出 #2
8
输入 #3
3 2 2
输出 #3
40