Petya and Coloring
题意翻译
题目描述
--
$Petya$喜欢计数。他想计算:
用$K$种颜色绘制尺寸为$n*m$ ( $n$行,$m$列)的矩形棋盘的方法数。
此外,着色应满足以下要求:
对于沿格子的线穿过的任何垂直线,会将棋盘分成两个非空的部分,这两个部分中的不同颜色的数量应相同。
帮助$Petya$对这些颜色进行计数。
输入格式
---
第一行有三个用空格隔开的整数$n$,$m$,$k$ $(1<=n,m<=1000,1<=k<=1e6)$
含义如题。
输入共一行。
输出格式
--
输出如题要求的答案。由于答案可能过大,输出其模$1e9+7$的值。
题目描述
Little Petya loves counting. He wants to count the number of ways to paint a rectangular checkered board of size $ n×m $ ( $ n $ rows, $ m $ columns) in $ k $ colors. Besides, the coloring should have the following property: for any vertical line that passes along the grid lines and divides the board in two non-empty parts the number of distinct colors in both these parts should be the same. Help Petya to count these colorings.
输入输出格式
输入格式
The first line contains space-separated integers $ n $ , $ m $ and $ k $ ( $ 1<=n,m<=1000,1<=k<=10^{6} $ ) — the board's vertical and horizontal sizes and the number of colors respectively.
输出格式
Print the answer to the problem. As the answer can be quite a large number, you should print it modulo $ 10^{9}+7 $ ( $ 1000000007 $ ).
输入输出样例
输入样例 #1
2 2 1
输出样例 #1
1
输入样例 #2
2 2 2
输出样例 #2
8
输入样例 #3
3 2 2
输出样例 #3
40