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

問題を読み込み中...

本文、提出履歴、提出フォームを準備しています。

作問者: rootenterテスター: nflight11

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{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}.

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

$N$

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

例 1

入力例

出力例

例 2

入力例

出力例