Farmer John has come up with a new morning exercise routine for the cows (again)!
As before, Farmer John's n cows are standing in a line. The i-th cow from the left has label i for each i (1 ≤ i ≤ n). He tells them to repeat the following step until the cows are in the same order as when they started.
Given a permutation A of length n, the cows change their order such that the i-th cow from the left before the change is A[i]
-th from the left after the change.
For example, if A = (1, 2, 3, 4, 5) then the cows perform one step and immediately return to the same order. If A = (2, 3, 1, 5, 4), then the cows perform six steps before returning to the original order. The order of the cows from left to right after each step is as follows:
0 steps: (1, 2, 3, 4, 5)
1 step: (3, 1, 2, 5, 4)
2 steps: (2, 3, 1, 4, 5)
3 steps: (1, 2, 3, 5, 4)
4 steps: (3, 1, 2, 4, 5)
5 steps: (2, 3, 1, 5, 4)
6 steps: (1, 2, 3, 4, 5)
Compute the product of the numbers of steps needed over all n! possible permutations A of length n.
As this number may be very large, output the answer modulo m.
Contestants using C++ may find the following code from KACTL helpful. Known as the Barrett reduction, it allows you to compute a % b several times faster than usual, where b > 1 is constant but not known at compile time. (we are not aware of such an optimization for Java, unfortunately).
The first line contains n (1 ≤ n ≤ 7500) and m (10^8
≤ m ≤ 10^9
+ 7, m is prime).
Print a single integer.
For each i (1 ≤ i ≤ n), the i-th element of the following array is the number of permutations that cause the cows to take i steps: [1, 25, 20, 30, 24, 20]. The answer is 1^1
* 2^25
* 3^20
* 4^30
* 5^24
* 6^20
= 369329541 (mod 10^9
+ 7).