Guest User

Untitled

a guest
Nov 4th, 2014
483
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.33 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstdlib>
  5. #include <vector>
  6. #include <set>
  7. #include <map>
  8. #include <cassert>
  9. #include <ctime>
  10. #include <cmath>
  11. #include <string>
  12. #include <cstring>
  13. #include <queue>
  14. using namespace std;
  15.  
  16. #define f first
  17. #define s second
  18. #define mp make_pair
  19. #define pb push_back
  20. #define pii pair<int, int>
  21. #define vi vector<int>
  22. #define all(v) (v).begin(), (v).end()
  23. #define forit(it,v) for (__typeof(v.begin()) it = v.begin(); it != v.end(); ++it)
  24. #define f0(a) memset(a, 0, sizeof(a))
  25. #define ll long long
  26. const int mod = (int)1e9+7;
  27. ll n;
  28. int k;
  29. int inv[100000];
  30.  
  31. int modPow(int a, int n) {
  32.     int res = 1;
  33.     while (n > 0) {
  34.         if (n & 1) res = 1ll * res * a % mod;
  35.         a = 1ll * a * a % mod;
  36.         n >>= 1;
  37.     }
  38.     return res;
  39. }
  40.  
  41. int main() {
  42.     freopen("power.in", "r", stdin);
  43.     freopen("power.out", "w", stdout);
  44.     cin >> n >> k;
  45.     for (int i = -k-1; i <= k+1; ++i)
  46.         inv[i + k+1] = modPow((mod + i) % mod, mod - 2);
  47.    
  48.     int nn = n % mod;
  49.     int ans = 0, val = 0;
  50.  
  51.     for (int i = 1; i <= k + 2; ++i) {
  52.         val = (val + modPow(i, k)) % mod;
  53.         int cur = val;
  54.         for (int j = 1; j <= k + 2; ++j) if (i != j) { 
  55.             cur = 1ll * cur * (nn - j + mod) % mod;
  56.             cur = 1ll * cur * inv[i-j+k+1] % mod;
  57.         }
  58.         ans = (ans + cur) % mod;
  59.     }
  60.     cout << ans << endl;
  61.     return 0;
  62. }
Advertisement
Add Comment
Please, Sign In to add comment