Statement양의 정수 NNN이 주어질 때 다음의 행렬 AAA에 대하여 det(A)\det(A)det(A)를 계산하자. 이때 행렬 AAA의 iii행 jjj열 성분은 다음과 같다: Aij=(igcd(i,j))(1≤i,j≤n).A_{ij} = \left( \frac{i}{\gcd(i,j)} \right) \quad (1 \le i,j \le n).Aij=(gcd(i,j)i)(1≤i,j≤n). 즉, 구해야하는 값은, ∣1gcd(1,1)1gcd(1,2)⋯1gcd(1,N)2gcd(2,1)2gcd(2,2)⋯2gcd(2,N)⋮⋮⋱⋮Ngcd(N,1)Ngcd(N,2)⋯Ngcd(N,N)∣. \begin{vmatrix} \frac{1}{\gcd(1,1)} & \frac{1}{\gcd(1,2)} & \cdots & \frac{1}{\gcd(1,N)} \\ \frac{2}{\gcd(2,1)} & \frac{2}{\gcd(2,2)} & \cdots & \frac{2}{\gcd(2,N)} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{N}{\gcd(N,1)} & \frac{N}{\gcd(N,2)} & \cdots & \frac{N}{\gcd(N,N)} \\ \end{vmatrix}.gcd(1,1)1gcd(2,1)2⋮gcd(N,1)Ngcd(1,2)1gcd(2,2)2⋮gcd(N,2)N⋯⋯⋱⋯gcd(1,N)1gcd(2,N)2⋮gcd(N,N)N.Input입력은 다음과 같은 형식으로 주어진다.NNNOutput첫째 줄에 det(A)\det(A)det(A)를 1 000 000 0071\ 000\ 000\ 0071 000 000 007으로 나눈 나머지를 출력하여라.Constraints 1≤N≤10 000 0001 \leq N \leq 10\ 000\ 0001≤N≤10 000 000. Subtasks#점수제한110N≤8N \leq 8N≤8.218N≤500N \leq 500N≤500.327N≤100 000N \leq 100\ 000N≤100 000.445추가적인 제약조건이 없다.Samples예제 1입력복사1출력복사1예제 2입력복사5출력복사8태그 보기해설해설 보기
