Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 386  Solved: 296

[][][]

Description

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想知道这个矩阵的行列式的值，你能求出来吗?

Input

一个正整数n mod1000000007

n<=1000000

Output

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

Sample Input

5

Sample Output

16

HINT

 

Source

 

Orz PoPoQQQ

高斯消元之后发现对角线是欧拉函数。。

然后就做完了。

// luogu-judger-enable-o2#include
     
      #include
      
       #define LL long long using namespace std;const int MAXN = 1e7 + 10, mod = 1e9 + 7;int N;LL ans = 1;int prime[MAXN], tot, vis[MAXN], phi[MAXN];void GetPhi(int N) {    phi[1] = 1;    for(int i = 2; i <= N; i++) {        if(!vis[i]) prime[++tot] = i, phi[i] = i - 1;        for(int j = 1; j <= tot && i * prime[j] <= N; j++) {            vis[i * prime[j]] = 1;            if(i % prime[j] == 0) phi[i * prime[j]] = phi[i] * prime[j];            else phi[i * prime[j]] = phi[i] * phi[prime[j]];        }    }}int main() {    scanf("%d", &N);    GetPhi(1e6 + 10);    for(int i = 1; i <= N; i++) ans = (1ll * ans * phi[i]) % mod;    printf("%lld", ans);    return 0;}/*123 321*/