Вправа (Платина)

Фермер Джон знову придумав новий режим ранкової зарядки для своїх корів!

Як і раніше, $n$ корів фермера Джона вишикувались в лінію. $i$-та корова зліва має мітку $i$ для кожного $i$ (1 \leq i \leq n). Він каже їм повторювати наступний крок доти, поки корови не повернуться в початковий порядок.

Дано перестановку $A$ довжини $n$, корови змінюють свій порядок так, що $i$-та корова зліва до зміни стає A_i-ою зліва після зміни.

Наприклад, якщо A = (1, 2, 3, 4, 5), то корови здійснюють один крок. Якщо A = (2, 3, 1, 5, 4), то корови здійснять шість кроків. Порядок корів зліва направо після кожного кроку буде наступним:

$0$ крок: (1, 2, 3, 4, 5)

$1$ крок: (3, 1, 2, 5, 4)

$2$ крок: (2, 3, 1, 4, 5)

$3$ крок: (1, 2, 3, 5, 4)

$4$ крок: (3, 1, 2, 4, 5)

$5$ крок: (2, 3, 1, 5, 4)

$6$ крок: (1, 2, 3, 4, 5)

Обчисліть добуток кількості кроків, необхідних для всіх $n!$ можливих перестановок $A$ довжини $n$.

Оскільки це число може бути дуже великим, виведіть відповідь за модулем $m$.

Учасники, які використовують C++, можуть знайти наступний код з KACTL корисним. Відомий як редукція Барретта, він дозволяє обчислювати $a$ % $b$ в кілька разів швидше звичайного, де b > 1 константа, невідома під час компіляції (на жаль, нам не відомо про таку оптимізацію для 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
}