Задача . Exercise

\(N\) коров (\(1\le N\le 7500\)) фермера Джона стоят в ряд. \(i\)-ая слева корова имеет метку \(i\) для всех \(1\le i\le N\). ФД говорит им повторять следующий шаг до тех по пока коровы не вернутся в исходное положение.

• По заданной перестановке \(A\) длины \(N\), коровы изменяют свой порядок \(i\)-ая корова слева до изменений становится \(A_i\)-ой коровой слева после изменения.

Например, если \(A=(1,2,3,4,5)\) тогда коровы выполнят один шаг и сразу вернутся в исходное положение. If \(A=(2,3,1,5,4)\), то коровы выполнят 6 шагов прежде чем вернутся в исходное положение. Порядок коров слева направо после каждого шага будет таким:

• 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\) (\(10^8\le M\le 10^9+7\), \(M\) - простое).

Контестанты, использующие C++, могут найти полезным следующий код KACTL Известный как Barrett reduction, он позволяет Вам вычислить \(a \% b\) в несколько раз быстрее, чем обычно. где \(b>1\) постоянная величина, но не известная во время компиляции. (К несчастью, мы не позаботились о такой оптимизации для Java).

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

typedef unsigned long long ull;
typedef __uint128t 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
}

369329541