Modulus of sum of sequence of Fibonacci numbers What is the most efficient way to find the modulus of sum of sequence of fibinacci numbers. 
For example (F(N) + F(N + 1) + ... + F(M)) mod 1000000007.
 A: Let $S(n)$ be the sum of first $n$ fibonacci modulo MOD( in you case MOD=1000000007).
What you want to find is $answer=(S(M)-S(N-1)) \% { MOD}$. If $awswer$ if negative, then $answer=answer+MOD$. So we have to basically find $S(n)$ for any $n$ efficiently. This can be done in $O(logn)$ by matrix exponentiation. First built the recurrence in matrix form and then calculate the power of a matrix modulo MOD efficiently using matrix exponentiation.( here $F(n)$ denotes $n$th fibonacci number, you will have to take
care of base cases, I have assumed 1 base index numbering ).
$$
 \left( \begin{array}{cc}
F(n) \\
F(n-1)\\
S(n)
\end{array} \right)
%
=
\left( \begin{array}{cc}
1 & 1 & 0 \\
1 & 0 & 0 \\
1 & 1 & 1
\end{array} \right)
%
 \left( \begin{array}{cc}
F(n-1) \\
F(n-2)\\
S(n-1)
\end{array} \right)
$$
Thus by repeatedly applying this relation we get for $n>=3$
$$
 \left( \begin{array}{cc}
F(n) \\
F(n-1)\\
S(n)
\end{array} \right)
%
=
{\left( \begin{array}{cc}
1 & 1 & 0 \\
1 & 0 & 0 \\
1 & 1 & 1
\end{array} \right)}^{n-2}
%
 \left( \begin{array}{cc}
1 \\
1  \\
2
\end{array} \right)
$$
So you just have to calculate the power of this first matrix  on RHS of equation. This can be done $O(logn)$ by matrix representation. You can read about it more here it is easy to understand, http://community.topcoder.com/tc?module=Static&d1=features&d2=0104. Just remember what ever multiplication , addition you are doing while matrix exponentiation do it modulo MOD.
A: First, note that $$\sum_{i=1}^nF_i = F_{n+2}-1$$
so your sequence reduces as follows:
$$\sum_N^MF_i = \sum_1^MF_i - \sum_1^{N-1}F_i = F_{M+2}-F_{N+1}$$
Then those two Fibonacci numbers can be generated without going through the entire sequence using 
$$ \begin{align} 
 F_{2n-1} &= F_n^2 + F_{n-1}^2\\
 F_{2n}   &= (2F_{n-1}+F_n)F_n 
\end{align}$$
All of which can be done modulo some chosen base.
