Exercise (Platinum)

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 \le i \le 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).

"'cpp #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) « ""; // 10000000073 3 "'