#209 Sign Processing Practice

Loading problem...

Preparing the statement, recent submissions, and submit form.

Authors: rootenterTesters: 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$ 으로 나눈 나머지를 출력하여라.

Sample 1

Input

Output

Sample 2

Input

Output