It is easy to prove that the answer for the query is ~\sum_{n=l}^r \binom{F_{n+2}}{k} = \sum_{n=0}^r \binom{F_{n+2}}{k} - \sum_{n=0}^{l-1} \binom{F_{n+2}}{k}~, where ~F_n~ are Fibonacci numbers. Let's notice, that ~\binom x k~ is a polynomial for ~x~ and can be expressed in the form ~c_0 + c_1 x + \dots + c_k x^k~. Knowing this, we can express the answer in a different way:

$$\displaystyle \sum_{n=0}^r \binom{F_{n+2}}{k} = \sum_{n=0}^r \sum_{m=0}^k c_m F_{n+2}^m = \sum_{m=0}^k c_m \sum_{n=0}^r F_{n+2}^m$$

Thus we reduced our problem to computing the sum of ~m^\text{th}~ powers of Fibonacci numbers. To do so we will refer to Binet's formula:

$$\displaystyle \begin{align*} F_n &= \frac{1}{\sqrt 5} \left(\left(\frac{1+\sqrt 5}{2}\right)^n - \left(\frac{1-\sqrt 5}{2}\right)^n\right) \\ &= \frac{\sqrt 5}{5} (\phi^n - \psi^n) \\ F_n^m &= \left(\frac{\sqrt 5}{5}\right)^m (\phi^n - \psi^n)^m \\ &= \left(\frac{\sqrt 5}{5}\right)^m \sum_{j=0}^m (-1)^{m-j} \binom j m \phi^{nj} \psi^{n(m-j)} \\ \sum_{n=0}^r F_n^m &= \left(\frac{\sqrt 5}{5}\right)^m \sum_{n=0}^r \sum_{j=0}^m (-1)^{m-j} \binom j m (\phi^j \psi^{m-j})^n \\ &= \left(\frac{\sqrt 5}{5}\right)^m \sum_{j=0}^m (-1)^{m-j} \binom j m \sum_{n=0}^r (\phi^j \psi^{m-j})^n \end{align*}$$

The inner sum is almost always a geometric progression with ~b_0 = 1~ and ~q = \phi^j \psi^{m-j}~, except for the cases when ~\phi^j \psi^{m-j} = 1~, but we may avoid any special cases by computing it in a way similar to binary exponentiation.

Indeed, in order to compute ~\sum_{n=0}^r q^n~, we may start with computing ~\sum_{n=0}^{2^k-1} q^n~ and ~q^{2^k}~. Two sums with ~m_1~ and ~m_2~ elements can be merged together in the following way:

$$\displaystyle \sum_{n=0}^{m_1+m_2-1} q^n = \sum_{n=0}^{m_1-1} q^n + q^{m_1} \sum_{n=0}^{m_1+m_2-1} q^n$$

Thus we can compute the sum of ~m^\text{th}~ powers only with additions and multiplications. The only difficulty is that there is ~\sqrt 5~ present in these formulas (in ~\phi~ and ~\psi~) and there is no such number modulo ~10^9+7~. The solution to this is simple: let's never specify an exact value for it. This way we will always work with numbers of the form ~a + \sqrt 5 b~. The addition and multiplication of these numbers is fairly easy:

$$\displaystyle \begin{align*} (a + \sqrt 5 b) + (c + \sqrt 5 d) &= (a+c) + \sqrt 5 (b+d) \\ (a + \sqrt 5 b) \times (c + \sqrt 5 d) &= (ac+5bd) + \sqrt 5 (ad+bc) \end{align*}$$

These are the only operations that we require. The sum of Fibonacci numbers (which are integers) is also an integer, so the final result will never contain any ~\sqrt 5~. Thus we have solved this problem.