소의 체조

Farmer John이 소들을 위해 새로운 아침 체조를 또 만들었다!

이전과 마찬가지로 Farmer John의 $N$마리 소($1\le N\le 7500$)가 한 줄로 서 있다. 왼쪽에서 $i$번째 소의 이름표는 각 $1\le i\le N$에 대해 $i$이다. Farmer John은 소들이 처음과 같은 순서가 될 때까지 다음 단계를 반복하라고 시킨다.

• 길이 $N$의 순열 $A$가 주어졌을 때, 소들은 순서를 바꾸어, 바꾸기 전 왼쪽에서 $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$의 모든 $N!$개 순열 $A$에 대해 필요한 단계 수의 곱을 구하라.

이 수는 매우 클 수 있으므로 답을 $M$으로 나눈 나머지를 출력하라 ($10^8\le M\le 10^9+7$, $M$은 소수).

C++을 사용하는 참가자는 KACTL의 다음 코드가 도움이 될 수 있다. Barrett reduction이라 불리는 이 방법은 $b>1$이 컴파일 시점에 알려지지 않은 상수일 때 $a \% b$를 평소보다 몇 배 빠르게 계산할 수 있게 해 준다. (아쉽게도 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$과 $M$이 주어진다.

정수 하나를 출력한다.

각 $1\le i\le N$에 대해, 다음 배열의 $i$번째 원소는 소들이 $i$단계를 거치게 하는 순열의 개수이다: $\[1,25,20,30,24,20].$ 답은 $1^1\cdot 2^{25}\cdot 3^{20}\cdot 4^{30}\cdot 5^{24}\cdot 6^{20}\equiv 369329541\pmod{10^9+7}$이다.