カタラン数に近い計算． \(K\) に関する条件がなければ \({}_{N+M}C_{N}\) 通り．
\(K\) に関する条件を満たさない場合の数は，グリッドを考えると分かりやすい． ある直線があって，その直線で折り返した場合の数に一致する． 通ってはダメな点を列挙して，それらのうち初めて通るもので場合分けして 数え上げると，折り返す前後で1対1対応が作れる．
注意
もともと通るグリッドが細長いときは，折り返した形が長方形にならない． この場合は 0通り．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n, m , k;
cin >> n >> m >> k;
Comb<mint, ll(2e6)+5> co;
mint ans = co.nCr(n+m,n) - co.nCr(n+m,n-(k+1));
if(n > m+k) ans = 0;
cout << ans.val() << endl;
return 0;
}
