BZOJ 3288: Mato矩阵

/**************************************************************
    Problem: 3288
    User: BeiYu
    Language: C++
    Result: Accepted
    Time:432 ms
    Memory:9100 kb
****************************************************************/
 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long LL;
const int N = 1e6+50;
const LL p = 1e9+7;
 
int n;LL ans;
int pr[N],cp;
int phi[N];
 
void Pre() {
    phi[1]=1,ans=1;
    for(int i=2;i<=n;i++) {
        if(!phi[i]) phi[i]=i-1,pr[++cp]=i;
        for(int j=1;j<=cp && (LL)pr[j]*i<=n;j++) {
            if(i%pr[j]) {
                phi[i*pr[j]]=phi[i]*(pr[j]-1);
            }else {
                phi[i*pr[j]]=phi[i]*pr[j];
            }
        }
    }
//  for(int i=1;i<=n;i++) cout<<phi[i]<<" ";cout<<endl;
    for(int i=1;i<=n;i++) ans=(ans*phi[i])%p;
}
 
int main() {
    cin>>n;
    Pre();
    cout<<ans<<endl;
    return 0;
}