Bài Tập Thể Dục

Điểm: 0,50 (OI)

Giới hạn thời gian: 4.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Java, Javascript, Kotlin, Pascal, Python, Scratch

Có $N$ con bò đứng thành hàng, được đánh số từ $1$ đến $N$ . Một hoán vị $A$ là một cách sắp xếp lại các con bò, trong đó con bò ở vị trí $i$ sẽ di chuyển đến vị trí $A_{i}$ .

Chu kỳ của một hoán vị $A$ là số bước tối thiểu để tất cả các con bò trở về vị trí ban đầu của chúng (tức là số bước nhỏ nhất $t > 0$ sao cho áp dụng $A$ đúng $t$ lần cho kết quả là hoán vị đồng nhất). Chu kỳ này bằng BCNN (bội chung nhỏ nhất) của độ dài tất cả các chu kỳ trong phân rã chu kỳ của hoán vị $A$ .

Hãy tính tích của chu kỳ trên tất cả $N!$ hoán vị có thể của $N$ con bò, lấy phần dư theo $M$ .

Dữ liệu vào

Một dòng duy nhất chứa hai số nguyên $N$ và $M$ .

Dữ liệu ra

Một số nguyên duy nhất là tích của chu kỳ trên tất cả $N!$ hoán vị, lấy phần dư theo $M$ .

Ràng buộc

$1 \leq N \leq 7500$
$10^{8} \leq M \leq 10^{9} + 7$ , $M$ là số nguyên tố

Ví dụ

Input	Output	Giải thích
5 1000000007	369329541	Tích của chu kỳ trên tất cả $5! = 120$ hoán vị của $5$ phần tử, lấy phần dư theo $10^{9} + 7$ .
8 908827567	182247740	Tích của chu kỳ trên tất cả $8! = 40320$ hoán vị của $8$ phần tử, lấy phần dư theo $908827567$ .

Ghi chú

Với $N = 5$ , có $120$ hoán vị. Ví dụ, hoán vị $[2, 1, 4, 5, 3]$ có các chu kỳ $(1 2) (3 4 5)$ , độ dài lần lượt là $2$ và $3$ , nên chu kỳ là $BCNN (2, 3) = 6$ . Tích tất cả các chu kỳ lấy phần dư theo $10^{9} + 7$ bằng $369329541$ .

Bình luận

Không có bình luận tại thời điểm này.