Mato矩阵

时间限制:10s      空间限制:128MB

题目描述

Mato同学最近正在研究一种矩阵,这种矩阵有n行n列第i行第j列的数为gcd(i,j)。
例如n=5时,矩阵如下:

1 1 1 1 1
1 2 1 2 1
1 1 3 1 1
1 2 1 4 1
1 1 1 1 5

Mato想知道这个矩阵的行列式的值,你能求出来吗?


输入格式

一个正整数n mod1000000007


输出格式

n行n列的Mato矩阵的行列式。


样例输入

5


样例输出

16


 

提示

对于100%的数据,n<=1000000。


题目来源

By taorunz