Bảng màu

View as PDF

Submit solution

Points: 1.63 (partial)
Time limit: 0.6s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
TCO 2011 Round 3
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho một bảng kích thước ~M \times N~. George có tất cả ~K~ màu khác nhau. Cậu muốn tô màu bảng này sao cho:

Mỗi màu được sử dụng ít nhất một lần ở dòng trên cùng của bảng

~2~ ô cùng màu phải thuộc cùng ~1~ thành phần liên thông

~2~ cách tô màu được gọi là khác nhau nếu dòng trên cùng của ~2~ bảng là khác nhau. Đếm số cách tô màu có thể, lấy modulo ~10^{9} + 7~

Input

  • Dòng ~1~: ~3~ số nguyên ~M~, ~N~, ~K~ ~(0~ \< ~M~, ~N~, ~K \leq 300)~

Output

  • Một dòng đưa ra số cách tô màu có thể.

Sample Input 1

4 1 2

Sample Output 1

6

Sample Input 2

4 3 2

Sample Output 2

12

Sample Input 3

4 4 10

Sample Output 3

0

Sample Input 4

14 28 14

Sample Output 4

178290591

Note

Trong test ví dụ số ~1~, ~6~ cách tô màu là "AAAB", "AABB", "ABBB", "BBBA", "BBAA" và "BAAA".

Trong test ví dụ số ~2~, có thêm ~6~ cách tô màu dòng đầu tiên. Bảng sau đây mô tả một số cách tô hợp lệ:

ABAA AABA ABBA BABB BBAB BAAB

ABBA AAAA ABAA BABB BAAB BBBB

AAAA AAAA AAAA BBBB BBBB BBBB


Comments

Please read the guidelines before commenting.


There are no comments at the moment.