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=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