Giải bài trực tuyến

Cho một bảng kích thước M * 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 <= 300)

Output:

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

Example:

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