← 返回题目列表

Codeforces · 111/D

D. Petya 和着色

中文机器翻译题面 查看原题

小彼佳喜欢数数。他想计算用 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