Counting subsets containing three consecutive elements (previously Summation over large values of nCr) Problem: In how many ways can you select at least $3$ items consecutively out of a set of $n ( 3\leqslant n \leqslant10^{15}$) items. Since the answer could be very large, output it modulo $10^{9}+7$.
Example:
for $n=4 ({abcd})$, 
answer = $3 (abc,bcd,abcd)$
I came up with this expression:
$$
\sum_{k=0}^{n-3} C^{n-3}_k + (n-3)\sum_{k=0}^{n-4} C^{n-4}_k
$$
The values n could take is so large that the above expression will take ages to be computed. I have no idea of how to simplify it.
Also, because this is an algorithmic problem, there's a time constraint of $5$ sec.
How do I compute the answer within the given time constraint?
 A: The question can be reduced to 

How many bit strings of $0's$ and $1's$ are there so that there are three consecutive $1's$.

Here $1$ means object is selected and $0$ means not selected.  
Let $a_n$ denote the number of bit strings of length $n$ that contain three consecutive $1's$.That will be equal to the number of bit strings of length $n-1$ that contain three consecutive $1's$ with a $0$ added to the end plus (because we have not included the case when last bit is $1$) the number of bit strings of length $n-2$ that contain three consecutive $1's$ with a $10$ added to the end plus (because we have not included the case when last two bit is $11$) the number of bit strings of length $n-3$ that contain three consecutive $1's$ with $110$ added to the end plus the number of bit strings of length $n-3$ with $111$ added to the end (in this case we have to consider all the possibilities of remaining $n-3$ bits )
Hence the recurrence relation will be 
$$ a_n = a_{n-1} + a_{n-2} + a_{n-3} + 2^{n-3}$$
for $n>3$ and $a_1 = 0, a_2 = 0,  a_3 = 1$.
See this to solve this recurrence.
A: Hint:  how many total subsets are there of a set of size $n$?  How many of them have $0, 1,$ or $2$ elements?  Now you are summing only $3$ items, not $n-3$.
