[原创]51nod 1189 阶乘分数 [因子个数+逆元]【数论】

# include <bits/stdc++.h>
using namespace std;
# define abs(x) ((x>=0)?(x):-(x))
typedef long long int LL;
const int MOD = 1e9+7;
const int N = 1e6+7;
/*******************************************/
int prime[N],kp;
int Is_or[N][2];
void Prime(){
    kp = 0;
    memset(Is_or,true,sizeof(Is_or));
    Is_or[0][0]=Is_or[1][0]=0;
    for(int i=2;i<=1000000;i++){
        if(Is_or[i][0]) Is_or[i][1]=kp,prime[kp++]=i;
        for(int j=0;j<kp&&prime[j]*i<=1000000;j++){
            Is_or[prime[j]*i][0]=0;
            if(0==i%prime[j]) break;
        }
    }
    return ;
}
LL a[80000];
LL qmod(LL a,LL b){
    LL res= 1ll;
    while(b){
        if(b&1)res=res*a%MOD;
        b>>=1;
        a=a*a%MOD;
    }
    return res;
}
int main(){
    //printf("%I64d\n",qmod(2,MOD-2));
    Prime();
    //printf("%d\n",kp);
    //for(int i=0;i<kp;i++)printf("%d\n",prime[i]);
    int n;
    scanf("%d",&n);
    int tem ;
    for(int i=1;i<=n;i++){
        tem = i;
        for(int j=0;j<kp&&tem>=prime[j];j++){
            if(Is_or[tem][0]) {a[Is_or[tem][1]]++;break;}
            while(0==tem%prime[j]) a[j]++,tem/=prime[j];
        }
    }
    LL ans = 1ll;
    for(int i=0;i<kp;i++){
        ans*=((a[i]<<1)+1);
        ans%=MOD;
    }
    printf("%I64d\n",(ans+1)*500000004%MOD);
    return 0;
}