Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <cstdlib>
- #include <vector>
- #include <set>
- #include <map>
- #include <cassert>
- #include <ctime>
- #include <cmath>
- #include <string>
- #include <cstring>
- #include <queue>
- using namespace std;
- #define f first
- #define s second
- #define mp make_pair
- #define pb push_back
- #define pii pair<int, int>
- #define vi vector<int>
- #define all(v) (v).begin(), (v).end()
- #define forit(it,v) for (__typeof(v.begin()) it = v.begin(); it != v.end(); ++it)
- #define f0(a) memset(a, 0, sizeof(a))
- #define ll long long
- const int mod = (int)1e9+7;
- ll n;
- int k;
- int inv[100000];
- int modPow(int a, int n) {
- int res = 1;
- while (n > 0) {
- if (n & 1) res = 1ll * res * a % mod;
- a = 1ll * a * a % mod;
- n >>= 1;
- }
- return res;
- }
- int main() {
- freopen("power.in", "r", stdin);
- freopen("power.out", "w", stdout);
- cin >> n >> k;
- for (int i = -k-1; i <= k+1; ++i)
- inv[i + k+1] = modPow((mod + i) % mod, mod - 2);
- int nn = n % mod;
- int ans = 0, val = 0;
- for (int i = 1; i <= k + 2; ++i) {
- val = (val + modPow(i, k)) % mod;
- int cur = val;
- for (int j = 1; j <= k + 2; ++j) if (i != j) {
- cur = 1ll * cur * (nn - j + mod) % mod;
- cur = 1ll * cur * inv[i-j+k+1] % mod;
- }
- ans = (ans + cur) % mod;
- }
- cout << ans << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment