Фермер Джон (снова) придумал новый режим утренней зарядки для коров!
Как и прежде, 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).
В одной строке заданы числа 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).