Вправа (Платина)
Фермер Джон знову придумав новий режим ранкової зарядки для своїх корів!
Як і раніше, n корів фермера Джона вишикувались в лінію. i-та корова зліва має мітку i для кожного i (1 ≤ i ≤ 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
}Вхідні дані
В одному рядку задані числа n (1 ≤ n ≤ 7500) і m (10^8 ≤ m ≤ 10^9 + 7, m просте).
Вихідні дані
Виведіть одне число.
Приклад
Для кожного i (1 ≤ i ≤ n), i-ий елемент наступного масиву - це кількість перестановок, які змушують корів робити i кроків: [1, 25, 20, 30, 24, 20]. Відповідь дорівнює 1^1 * 2^25 * 3^20 * 4^30 * 5^24 * 6^20 = 369329541 (mod 10^9 + 7).