ABC021 D問題 多重ループ

1≦a1≦a2≦…≦ak≦n であるような整数の組 (a1,a2,…,ak) の個数を求める問題。
これって冷静に考えれば重複組み合わせだからcombination(n+k-1, k-1)じゃん…
なんかちょっとむずかしいことしてみたけど結局求めているものは一緒です…はぁ…

const ll mod = (ll)1e9+7;

template<class T>
T extgcd(T a, T b, T &x, T &y) {
    T g = a;
    if(b != 0){
        g = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    }else{
        x = 1;
        y = 0;
    }
    return g;
}

template<class T>
T mod_inverse(T a, T m)
{
    T x, y;
    extgcd(a, m, x, y);
    return (x % m + m) % m;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll N,K; cin >> N >> K;
    ll ans = 1;
    ll now = 1;
    for(ll i=1; i<N; i++){
        now *= (K-1+i);
        now %= mod;
        now *= mod_inverse<ll>(i,mod);
        now %= mod;
        ans = (ans+now)%mod;
    }
    cout << ans << endl;
}