小 Petya 喜欢数数。他想统计用 k 种颜色给一块 n×m 的方格板(n 行、m 列)染色的方案数,要求染色方案满足如下性质:对任何一条沿网格线把板子分成两个非空部分的竖线,两部分中不同颜色的数量都相同。请帮 Petya 数出这些染色方案。
第一行包含用空格隔开的整数 n、m 和 k(1≤n,m≤1000,1≤k≤106),分别表示板子的竖直与水平尺寸以及颜色种数。
输出问题的答案。由于答案可能非常大,对 109+7 取模后输出。
2 2 1
1
2 2 2
8
3 2 2
40