|
|
back to boardtl # include <cstdio> # include <iostream> # include <vector> # include <cstring> # include <algorithm> # include <map> # include <string> # include <set> # include <cmath> using namespace std; const int M = 1e9 + 7; const int N = 1000001; int a[N], n, f[N], prime[170], sz; bool used[N]; void get_primes(){ for (int i = 2; i < 1001; i ++){ for (int j = i + i; j < 1001; j += i) used[j] = true; } for (int i = 2; i < 1001; i ++){ if (!used[i]) prime[sz++] = i; } } int main(){ scanf("%d", &n); get_primes(); f[1] = f[2] = 1; for (int i = 3; i <= n; i ++){ f[i] = f[i - 1] + f[i - 2]; if (f[i] >= M) f[i] -= M; } for (int i = n; i > 1; i --){ int p = i; for (int j = 0; j < sz && prime[j] * prime[j] <= p; j ++){ while (p % prime[j] == 0){ p /= prime[j]; a[prime[j]] += f[n - i + 1]; if (a[prime[j]] >= M) a[prime[j]] -= M; } } if (p > 1){ a[p] += f[n - i + 1]; if (a[p] >= M) a[p] -= M; } } long long ans = 1; for (int i = 1; i <= n; i ++){ ans = (ans * long long((a[i] + 1) % M)) % M; } printf("%lld", ans); return 0; } |
|
|