This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD = 1000000007;
LL powmod(LL a, LL n){
if(n == 0) return 1;
if(n % 2) return (a * powmod(a, n-1)) % MOD;
LL c = powmod(a, n/2);
return (c * c) % MOD;
}
LL inv(LL a){
return powmod(a, MOD-2);
}
LL fact[110000];
LL invfact[110000];
int main(){
fact[0] = invfact[0] = 1;
for(LL i = 1; i < 110000; i++){
fact[i] = (i * fact[i-1]) % MOD;
invfact[i] = inv(fact[i]);
}
LL n, k;
cin >> n >> k;
k--;
LL ans = 0;
for(LL i = 0; i <= k; i++){
LL cur = powmod(k+1-i,n);
cur = (cur * fact[n+1]) % MOD;
cur = (cur * invfact[i]) % MOD;
cur = (cur * invfact[n+1-i]) % MOD;
if(i % 2) cur *= -1;
ans = (ans + cur) % MOD;
}
ans %= MOD;
if(ans < 0) ans += MOD;
cout << ans << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |