Bài Tập Thể Dục

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\le N\le 7500$
• ${10}^8\le M\le {10}^9+7$, $M$ là số nguyên tố

Ví dụ

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ỳ $(12)(345)$, độ dài lần lượt là $2$ và $3$, nên chu kỳ là $\text{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$.