Lễ hội hỗn loạn
Đề bài
Mô tả
Hằng năm, trường của Chikapu tổ chức một lễ hội Carnival vào tháng Ba để học sinh thư giãn trước kỳ thi cuối kỳ.
Năm nay, Chikapu phụ trách đoàn diễu hành của lễ hội. Có lớp, mỗi lớp cử đúng học sinh tham gia diễu hành. Trong lúc diễu hành, các học sinh được xếp thành một lưới gồm hàng và cột. Ô ở hàng , cột được ký hiệu là . Mỗi ô của lưới có đúng một học sinh. Để thể hiện sự đa dạng, Chikapu muốn không có hai học sinh cùng lớp nào đứng trong cùng một cột.
Chikapu tự hỏi có bao nhiêu cách sắp xếp khác nhau. Hai cách sắp xếp được coi là khác nhau nếu có ít nhất một ô có học sinh khác nhau đứng.
Vì số cách sắp xếp có thể rất lớn, hãy in ra kết quả theo modulo .
Dữ liệu vào
Dòng đầu tiên chứa số nguyên (): số bộ test. Mỗi bộ test gồm một dòng chứa hai số nguyên và ().
Dữ liệu ra
Với mỗi bộ test, in ra đáp án trên một dòng.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 1 2 2 |
16 | Có lớp và , mỗi lớp học sinh và . Mỗi cột phải gồm một học sinh lớp và một học sinh lớp , có tất cả cách sắp xếp hợp lệ. |
| 3 2 2 1 1 3 2 |
16 1 288 |
Với , chỉ có một học sinh nên chỉ có một cách. |
Bình luận