BALLGAME - Trò chơi với những viên bi
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: middlest

Tuy là Valentine nhưng An vẫn phải đi học T_T, may mắn thay lớp hôm nay vắng rất nhiều, chỉ còn thầy giáo và vài bạn nam (FA), vì vậy thầy quyết định tổ chức trò chơi đố vui, tất nhiên là có thưởng. Vì không được thông minh lắm nên đã đến câu cuối mà An vẫn chưa lấy được phần thưởng nào, quyết không để vừa FA vừa không có quà trong ngày Valentine, An muốn nhờ các NTUCoders giải câu đố này thật nhanh và chính xác để giúp cậu ấy vui! Nội dung câu đố như sau:

Cho một bảng gồm m dòng, n cột và 4 loại bi: xanh, đỏ, tím, vàng. Hãy đếm số cách xếp m*n viên bi vào bảng sao cho trên mỗi dòng phải có ít nhất k loại bi khác nhau, biết rằng hai cách xếp được gọi là khác nhau nếu có ít nhất một ô khác loại.

Vì số cách rất lớn nên chỉ cần in ra phần dư của kết quả khi chia cho 109+7

Dữ liệu vào

Gồm 1 dòng ghi 3 số m, n, k

Dữ liệu ra

Gồm 1 dòng ghi số cách xếp thỏa mãn yêu cầu bài toán

Giới hạn

1 <= m, n <= 106, 1 <= k <= 4

Ví dụ

  • input
    1 2 1
    output
    16
Back to Top