How to calculate sum of binomial coefficients efficiently?
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)$.


Then for a final answer:


   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)$.