ABC 31 D 多重ループ

をmod 1e9+7 での逆元を使いながら計算すれば良い。

最初 #define MOD 1000000007 としていたが、これだとMODはint型と判断されオーバーフローを起こしてしまってつらかった。

#include <bits/stdc++.h>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);i++)
typedef long long ll;

const ll MOD=1000000007;

ll inverse(ll a){
    ll res=1;
    ll base=a;
    REP(i,33){
        if(((MOD-2)>>i) & 1) res=(res*base)%MOD;
        base=(base*base)%MOD;
    }
    return res;
}

ll fact(ll a){
    ll res=1;
    for(int i=1;i<=a;i++) res=(res*i)%MOD;
    return res;
}

ll nHk(ll n, ll k){
    ll a=fact(n-1+k);
    ll b=inverse(fact(k));
    ll c=inverse(fact(n-1));
    return (((a*b)%MOD)*c)%MOD;
}

int main(){
	int n,k;
    cin >> n >> k;
    cout << nHk(n,k) << endl;
	return 0;
}