【題解】AtCoder ABC 156E – Roaming

#include <iostream>
using namespace std;
#define ll long long

const int maxn = 400005;
ll pre[maxn];
ll inv[maxn];
ll prei[maxn];
ll n, k, mod = 1000000007;

void build(int n){
    pre[1] = pre[0] = 1;
    inv[1] = inv[0] = 1;
    prei[1] = prei[0] = 1;
    for(int i = 2 ; i <= n ; i++){
        pre[i] = pre[i-1] * i % mod;
        inv[i] = (mod - mod / i * inv[mod % i] % mod) % mod;
        prei[i] = prei[i-1] * inv[i] % mod;
    }
}

ll C(int n, int k){
   return pre[n] * prei[k] % mod * prei[n-k] % mod;
}

int main() {
    build(maxn-2);
    cin >> n >> k;
    if (k >= n-1) cout << C(n+n-1, n-1);
    else{
        long long ans = C(n+n-1, n-1);
        for (int i = 1; i < n-k; i++){
            ans -= C(n-1, i-1)*C(n, i)%mod;
            ans += mod;
            ans %= mod;
        }
        cout << ans << "\n";
    }
}