How do I do sum of first k elements of a row of a Pascal's Triangle efficiently?

More specifically, I want to:

$^nC_0 + ^nC_1 + ^nC_2 + ..... + ^nC_k$

I tried doing it linearly by calculating $^nC_{j+1}$ by multiplying $^nC_{j}$ with (n-j+1)/j.

The answer it gives is correct for small numbers. Since n and k can be large, I need have keep modding with P, a given prime number.

My method fails since I have to divide with j, which breaks the mod.
Any suggestions?

Your method is fine. You just need to know how to do modular division. Modular division is a bit different from division of two integers. You can do modular division, say $x/y \bmod p$, by computing computing the modular inverse of $y$, $y^{-1}\bmod p$, and then multiplying that by $x$. You can compute the modular inverse using the extended Euclidean algorithm.

See https://en.wikipedia.org/wiki/Modular_multiplicative_inverse.

A slight correction:

$${n \choose j+1} = {n \choose j} \times {(n-j) \over j+1}.$$

You had an off-by-one error in the formula. To do this modulo $p$, replace dvision by $j+1$ with multiplication by the modular inverse of $j+1$ modulo $p$.

StackExchange Computer Science Q#59502, answer score: 2