← 返回题目

题库练习 Petya and Coloring

← 上一题下一题 →

A8189 | $Petya and Coloring$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

Little Petya loves counting. He wants to count the number of ways to paint a rectangular checkered board of size $n\timesm$ ( $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

输入 #2

2 2 2

输出 #2

输入 #3

3 2 2

输出 #3

C++ 编辑器

输入

输出