ROOKS - Lonely Rock
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 3.0 giây
Giới hạn bộ nhớ: 512 megabyte
Đăng bởi: a516ami_crush_tuyetni

Duy và Quý là đôi bạn trai rất thân thiết. Họ thường chơi cờ vua với nhau mỗi khi rảnh rỗi. Một ngày nọ, 

sau khi đã chơi chán chê cờ tiêu chuẩn, hai bạn cùng nghĩ ra một trò chơi khác để giải trí. Trong trò chơi này, họ chỉ sử dụng các con xe và đặt chúng lên các ô cờ mà họ thích. Vì Duy cực kỳ thích cờ vua nên nhà bạn ấy có rất nhiều bộ cờ khác nhau, đủ để họ có thể đặt bao nhiêu con xe tùy thích. Sau một lúc thay nhau đặt các con xe lên bàn cờ, Quý nhận thấy một số con xe rất cô đơn vì nó không có ai để chiến đấu cả: đó là các con xe nằm trên hàng và cột chỉ chứa một mình nó. Một câu hỏi tự nhiên xuất hiện trong đầu hai bạn: Liệu có bao nhiêu cách sắp xếp để không có con xe nào cảm thấy cô đơn?

Và vì cả hai bạn đều là học sinh trường chuyên Lê Quý Đôn, họ nhanh chóng nhận thấy kích thước bàn cờ và số lượng các con xe cô đơn không quá quan trọng. Nhưng như vậy vẫn chưa đủ giúp họ giải quyết đầy đủ vấn đề. Một lần nữa, với sự tư vấn từ Tuấn và Huy, họ quyết định đăng câu hỏi của mình lên diễn đàn DL. Các bạn hãy giúp Duy và Quý xác định xem có bao nhiêu cách xếp các con xe trên một bàn cờ kích thước m * n sao cho có đúng t con xe “cô đơn” nhé.

Lưu ý:

  • Một cách xếp chỉ hợp lệ khi mỗi ô cờ chỉ chứa tối đa 1 con xe.
  • Hai cách xếp được xem là khác nhau nếu tồn tại một ô cờ có xe ở cách này và không có xe ở cách còn lại.

Ví dụ

Input

2 2 4

0

1

2

3

Output

10

4

2

0

Back to Top