Использование концепции модульного мультипликативного обратного для вычисления nCr% MOD

Я рассчитываю nCr% MOD для больших значений n

Я использую соотношение (n + 1) Cr = (nCr) * (n + 1) / (n + 1-r)

Я должен перебрать цикл для разных значений n, сохраняя константу r.

llu fact=1;
/*The loop begins from i>=M+1 */
fact=(fact*(i-1)*modInverse(i-M,MOD))%MOD;  // Single statement executed during each iteration of loopHere I'm calculating (i-1)C(M-1)
Here M and MOD are constant values
MOD=1000000009 and llu refers to unsigned long long

Что я делаю именно

(n+1)Cr % MOD = [ (nCr) * (n+1) * modInverse(n+1-r) ] % MOD

Здесь modInverse вычисляет модульный мультипликативный обратный согласно следующему определению:

llu modPow(llu a, llu x, llu p)
{
//calculates a^x mod p
llu res = 1;
while(x > 0)
{
if( x % 2 != 0)
{
res = (res * a) % p;
}
a = (a * a) % p;
x /= 2;
}
return (res%MOD);
}
llu modInverse(llu a, llu p)
{
//calculates the modular multiplicative of a mod m assuming p is prime
return modPow(a, p-2, p);
}

Теперь проблема в том, что я не получаю правильные значения nCr для больших значений n (порядка 10 ^ 6). Является ли мой подход

(n+1)Cr % MOD = [ (nCr) * (n+1) * modInverse(n+1-r) ] % MOD

концептуально неправильно?