Calculate$ (n+m-1)C_n \mod 10^9+7$ efficiently

Question

I want to calculate $(n+m-1)C_n \mod 1000000007$. where $n$ can be between $1$ and $10^9$. $m$ will not exceed $30$. How do I calculate it efficiently.

Answer 1

Just use the standard expression $$ \binom nk=\frac {n(n-1)\ldots(n-k+1)}{k!} \text{ whence } \binom {n+m-1}m=\frac {(n+m-1)(n+m-2)\ldots n}{m!}, $$ while computing modulo $N=10^9+7$. You do the division using the modular inverses of $1,2,\ldots,m$ modulo $N$, which you can easily compute and tabulate. For $n$ very close to $N$ the numerator may contain a $0$, which will then also be the result, but this does not matter; the main point is the denominator cannot be $0$.