#209 Sign Processing Practice

#209 Sign Processing Practice

DOJ/MathDOJ/MathDOJ 1

Authors: rootenterTesters: nflight11

Time limit: 1500 ms
Memory limit: 1024 MB
Checker: TOKEN

문제

양의 정수 $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 \leq N \leq 10\ 000\ 000$ .

서브태스크

#	Score	Constraints
1	10	$N \leq 8$ .
2	18	$N \leq 500$ .
3	27	$N \leq 100\ 000$ .

예제

Sample 1

Input

1

Output

1

Sample 2

Input

5

Output

8

⋮

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