Nông dân John lại nghĩ ra một bài tập thể dục buổi sáng mới cho những con bò!

Như trước đây, \(N\) con bò của Nông dân John (\(1 \leq N \leq 7500\)) đang đứng thành một hàng. Con bò thứ \(i\) từ bên trái mang nhãn \(i\) với mỗi \(1 \leq i \leq N\). Ông yêu cầu chúng lặp lại bước sau cho đến khi những con bò trở về đúng thứ tự ban đầu:

• Cho một hoán vị \(A\) độ dài \(N\), những con bò thay đổi thứ tự sao cho con bò đứng thứ \(i\) từ bên trái trước khi thay đổi sẽ đứng thứ \(A_i\) từ bên trái sau khi thay đổi.

Ví dụ, nếu \(A=(1,2,3,4,5)\) thì những con bò thực hiện một bước và lập tức trở về cùng thứ tự. Nếu \(A=(2,3,1,5,4)\) thì những con bò thực hiện sáu bước trước khi trở về thứ tự ban đầu. Thứ tự của những con bò từ trái sang phải sau mỗi bước như sau:

• 0 bước: \((1,2,3,4,5)\)
• 1 bước: \((3,1,2,5,4)\)
• 2 bước: \((2,3,1,4,5)\)
• 3 bước: \((1,2,3,5,4)\)
• 4 bước: \((3,1,2,4,5)\)
• 5 bước: \((2,3,1,5,4)\)
• 6 bước: \((1,2,3,4,5)\)

Tính tích của số bước cần thiết ứng với tất cả \(N!\) hoán vị \(A\) độ dài \(N\) có thể có.

Vì số này có thể rất lớn, hãy in đáp án theo modulo \(M\) (\(10^8 \leq M \leq 10^9+7\), \(M\) là số nguyên tố).

Thí sinh sử dụng C++ có thể thấy đoạn mã sau từ KACTL hữu ích. Kỹ thuật này được gọi là phép giảm Barrett, cho phép bạn tính \(a \% b\) nhiều lần nhanh hơn thông thường, trong đó \(b>1\) là một hằng số nhưng không được biết tại thời điểm biên dịch. (Đáng tiếc là chúng tôi không biết một cách tối ưu tương tự dành cho Java.)

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
typedef __uint128_t L;
struct FastMod {
    ull b, m;
    FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
    ull reduce(ull a) {
        ull q = (ull)((L(m) * a) >> 64);
        ull r = a - q * b; // can be proven that 0 <= r < 2*b
        return r >= b ? r - b : r;
    }
};
FastMod F(2);

int main() {
    int M = 1000000007; F = FastMod(M);
    ull x = 10ULL*M+3;
    cout << x << " " << F.reduce(x) << "\n"; // 10000000073 3
}

Dữ liệu vào

Tệp exercise.in:

Dòng đầu tiên chứa \(N\) và \(M\).

Dữ liệu ra

Tệp exercise.out:

In một số nguyên duy nhất.

Lưu ý: Bài này có giới hạn bộ nhớ được mở rộng lên 512 MB.

Phân nhóm

• Test 2 thỏa mãn \(N=8\).
• Các test 3–5 thỏa mãn \(N \leq 50\).
• Các test 6–8 thỏa mãn \(N \leq 500\).
• Các test 9–12 thỏa mãn \(N \leq 3000\).
• Các test 13–16 không có ràng buộc bổ sung.

Ví dụ

5 1000000007

369329541

Nguồn

USACO 2020 US Open Contest, Platinum — Exercise

Tác giả bài: Benjamin Qi.