Đến giờ đấu bài rồi!
Đề bài
Mô tả
Tên các nhân vật đã được che đi vì lý do bản quyền.
Ka•ba S•to, giám đốc của Ka•baCorp và là Duelist số một Nhật Bản, lại một lần nữa chuẩn bị đánh bại đối thủ truyền kiếp M•to Y•gi. Đã nếm hết thất bại này đến thất bại khác, phần lớn nhờ "hào quang nhân vật chính" của Y•gi, lần này Ka•ba quyết định bỏ qua vẻ cao thượng thường ngày và tự mình dùng thủ đoạn.
Anh ta yêu cầu cả hai người chơi đấu bằng Duel Disk++ mới phát triển, thiết bị có khả năng tự động xáo bài. Là người phát minh ra Duel Disk++, Ka•ba biết chính xác cơ chế xáo bài hoạt động thế nào. Giả sử bộ bài của người chơi có lá. Sau một lần xáo, thiết bị chuyển lá bài đang ở vị trí thứ tới vị trí thứ (các vị trí được đánh số từ đến tính từ trên xuống), trong đó là một hoán vị của các số nguyên từ đến , riêng cho từng thiết bị. Từ kinh nghiệm trước đây, Ka•ba biết Y•gi luôn xếp bộ bài theo một thứ tự nhất định, và Y•gi luôn dùng thiết bị xáo bài đúng lần khi bắt đầu trận đấu. Để giành chiến thắng, Ka•ba cần lá bài thứ trong cách xếp ban đầu của Y•gi nằm ở vị trí thứ sau lần xáo. Để chắc chắn điều đó, Ka•ba sẽ bí mật thay đổi hoán vị trong Duel Disk++ của Y•gi trước trận đấu.
Cho số nguyên và số lần xáo , hãy giúp Ka•ba đếm số hoán vị thoả mãn yêu cầu.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên và (, ): số lá bài trong bộ bài của Y•gi và số lần Y•gi xáo bộ bài ban đầu.
Dòng thứ hai chứa số nguyên đôi một khác nhau (): cách sắp xếp bộ bài mong muốn.
Dữ liệu ra
In ra một số nguyên: số hoán vị mà Ka•ba có thể chọn để đạt mục đích, lấy phần dư khi chia cho .
Ràng buộc
- là một hoán vị của .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 2 2 4 3 1 5 |
2 | Ka•ba có thể chọn hoặc . |
| 6 120 1 2 3 4 5 6 |
720 | Có thể chứng minh rằng với mọi , bộ bài luôn trở về trạng thái ban đầu sau lần xáo, nên cả hoán vị đều thoả mãn. |
| 6 120 1 2 3 4 6 5 |
0 | Như ví dụ trên, sau lần xáo bộ bài luôn trở về trạng thái ban đầu, nên không có hoán vị nào thoả mãn. |
| 10 15 4 8 5 1 3 10 9 2 7 6 |
465 |
Bình luận