#209 부호 처리 연습 (1) - Divisor Orthogonality

문제를 불러오는 중...

지문, 최근 제출, 제출 폼을 준비하고 있습니다.

Statement

양의 정수 $N$ 이 주어질 때 다음의 행렬 $A$ 에 대하여 $\det(A)$ 를 계산하자. 이때 행렬 $A$ 의 $i$ 행 $j$ 열 성분은 다음과 같다:

A_{ij} = \left( \frac{i}{\gcd(i,j)} \right) \quad (1 \le i,j \le n).

즉, 구해야하는 값은,

∣ \begin{array}{cccc} \frac{1}{\gcd (1, 1)} & \frac{1}{\gcd (1, 2)} & \dots & \frac{1}{\gcd (1, N)} \\ \frac{2}{\gcd (2, 1)} & \frac{2}{\gcd (2, 2)} & \dots & \frac{2}{\gcd (2, N)} \\ ⋮ & ⋮ & ⋱ \end{array}

입력은 다음과 같은 형식으로 주어진다.

$N$

첫째 줄에 $\det(A)$ 를 $1\ 000\ 000\ 007$ 으로 나눈 나머지를 출력하여라.

예제 1

입력

출력

예제 2

입력

출력

⋮

\frac{N}{\gcd (N, 1)} & \frac{N}{\gcd (N, 2)} & \dots & \frac{N}{\gcd (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}.