# How to calculate sum of binomial coefficients efficiently?

I want to compute the sum

$$\binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\binom{n}{6}+\dots+\binom{n}{k} \bmod 10^9+7$$

where $n$ and $k$ can be up to $10^{14}$ and $k\le n$.

I found several links on stack overflow to calculate sum of binomial coefficients but none of them works on large constraints like $10^{14}$. I tried doing it by changing series using the relation $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$ and came up with a brute force solution which is of no use. Is there any way to do it efficiently?

This question is from the TCS codevita 2016 round 2 contest, which has ended.

• Could you describe your brute force solution in a little more detail? – adrianN Aug 22 '16 at 15:07
• @adrianN I used a loop to from 2 to k where on each iteration, I multiply (n-k)*(n-k-1) to Numerator and (k+1)*(k+2) to denominator of a variable whose initial value is n*(n-1)/2 and add this to sum and I initialized sum with (nC0+nC2). – srd091 Aug 22 '16 at 15:38

Hint: Use Lucas's theorem.

In general, any time a programming contest problem wants you to compute something mod $p$, check for opportunities to reduce everything mod $p$ before doing any further work.

## Spoilers

Don't peek at any hint until you've spent a good amount of time thinking about the previous one!

A more in-depth hint if the previous wasn't enough:

Let $p=10^9 + 7$. Use Lucas's theorem to express $\binom{n}{i}$ in terms of functions of $n \bmod p$ and $i \bmod p$. Simplify the resulting sum by grouping terms.

If that's still not enough of a hint:

Consider the case where $k$ is a multiple of $p$. You should be able to come up with an efficient algorithm for that whose running time is something like $O(k/p)$.

Generalize to the case where $k=ap+b$. You should be able to express this as a sum of the previous form, plus $b$ more terms. As a result you should be able to achieve a final running time of $O(p)$.