题目描述

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