| 
nCr mod M = ( Π(i in [1, r]) n-i+1 / i ) mod M
= Π(i in [1, r]) n-i+1 * inv(i) mod M
ということで、ループの i 回目の時点で nCi が求まる。その都度結果を保存していけば O(r) で nC0 から nCr まで計算できる。
もしくは、1!, 2!, ..., n! まで逆元も含めて求めておいて n!/(r! * (n-r)!) = n! * inv(r!) * inv((n-r)!) としてもいい。
