Selectivo 2 - P7

#include <cstdio>
#include <cstring>

using namespace std;

#define MOD 1000000007

bool p[1000001];
int f[1000001];

int main(){
    memset(p,true,sizeof p);

    for(int i = 2;i <= 1000000;++i)
        if(p[i] && i <= 1000)
            for(int j = i * i;j <= 1000000;j += i)
                p[j] = false;

    f[0] = f[1] = 1;

    for(int i = 2;i <= 1000000;++i){
        f[i] = f[i - 1] + f[i - 2];
        if(f[i] >= MOD) f[i] -= MOD;
    }

    int n;

    scanf("%d",&n);

    long long ans = 1;

    for(int i = 2;i <= n;++i){
        if(p[i]){
            int e = 0;

            for(int j = i;j <= n;j += i){
                int x = 0,aux = j;

                while(aux % i == 0){
                    aux /= i;
                    ++x;
                }

                e = (e + (long long)f[n - j] * x) % MOD;
            }

            ans = ans * (e + 1) % MOD;
        }
    }

    printf("%lld\n",ans);

    return 0;
}