Advertisement
Guest User

Untitled

a guest
Aug 20th, 2014
208
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.21 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstring>
  3. #include <cmath>
  4. #include <string>
  5. #include <vector>
  6. #include <queue>
  7. #include <map>
  8. #include <set>
  9. #include <bitset>
  10. #include <algorithm>
  11. #include <functional>
  12. #include <deque>
  13. #include <stack>
  14. #include <tuple>
  15.  
  16. #define INF 1000000000
  17. #define mod 1000000007
  18. #define MAXN 32005
  19. #define PI 3.14159265358979323846
  20.  
  21. using namespace std;
  22.  
  23. long long delims[1000005];
  24.  
  25. int prime[1000005];
  26.  
  27. void factorize(int n, int m)
  28. {
  29.     while(n != 1)
  30.     {
  31.         delims[prime[n]] += m;
  32.         delims[prime[n]] %= mod;
  33.         n /= prime[n];
  34.     }
  35. }
  36.  
  37. int main()
  38. {
  39.  
  40. #ifndef ONLINE_JUDGE
  41.     freopen("input.txt", "r", stdin);
  42.     //freopen("output.txt", "w", stdout);
  43. #endif
  44.  
  45.     for(int i = 1; i <= 1000000; i++)
  46.         prime[i] = i;
  47.  
  48.     for(long long i = 2; i <= 1000; i++)
  49.         if(prime[i] == i)
  50.             for(long long j = i * i; j <= 1000000; j += i)
  51.                 prime[j] = i;
  52.  
  53.     int n;
  54.     scanf("%d", &n);
  55.  
  56.     long long a = 0, b = 1, c = 1;
  57.     for(int i = n; i > 1; i--)
  58.     {
  59.         factorize(i, c);
  60.         c = (a + b) % mod;
  61.         a = b;
  62.         b = c;
  63.     }
  64.  
  65.     long long ans = 1;
  66.  
  67.     for(int i = 0; i <= n; i++)
  68.     {
  69.         //printf("%d ", delims[i]);
  70.         ans *= (delims[i] + 1);
  71.         ans %= mod;
  72.     }
  73.     //putchar('\n');
  74.  
  75.     printf("%d\n", ans);
  76. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement