\documentclass{maratona}

\begin{document}
\begin{ProblemaAutor}{}{O problema das Flores}{1}{256}{Arthur Andrade D'Olival}

O Jardineiro Bino é conhecido por seus canteiros de flores meticulosamente planejados. Este ano, ele decidiu criar um canteiro linear de comprimento \(n\). Para cada uma das \(n\) posições no canteiro, Bino plantará exatamente uma flor, que pode ser ou vermelha (V) ou branca (B).

Bino é um artista, e a estética é sua principal preocupação. Ele acredita que a beleza surge da variação, mas também da harmonia. Após muita deliberação, ele estabeleceu uma regra de ouro para seu jardim: \textbf{nunca devem existir mais do que \(m\) flores consecutivas da mesma cor}.

Por exemplo, se \(n=5\) e \(m=2\), uma sequência como \texttt{V V B V V} é perfeitamente válida. No entanto, uma sequência como \texttt{V B B B V} é \emph{inválida}, pois contém um bloco de 3 flores brancas (\texttt{B B B}), o que excede o limite \(m=2\). Da mesma forma, \texttt{V V V V B} também é inválida por conter 4 flores vermelhas consecutivas.

Bino está planejando o jardim e quer saber quantas opções de design ele realmente tem. Seu desafio é ajudar Bino a determinar o número total de arranjos distintos que ele pode criar para seu canteiro de comprimento \(n\), respeitando estritamente sua regra de monotonia (o limite de \(m\)).

\Entrada

A entrada contém dois inteiros separados por espaço, \(n\) e \(m\), onde \(n\) (\(1 \leq n \leq 1\,000\)) é o comprimento da sequência de flores e  \(m\) (\(1 \leq m \leq 1\,000\)) é o número máximo permitido de flores iguais consecutivas.

\Saida

Imprima um único número inteiro: o número total de sequências de flores válidas de comprimento \(n\) que satisfazem a restrição de Bino.

Como este número pode ser extremamente grande, sua resposta deve ser calculada e impressa \textbf{módulo \(10^9 + 7\)}.

\ExemploEntrada

\begin{Exemplo}
\texttt{1~1} & \texttt{2}\\
\rowcolor{gray!20}\texttt{2~2} & \texttt{4}\\
\texttt{2~1} & \texttt{2}\\
\end{Exemplo}



\Notas

Caso de teste 1: \(n=1, m=1\).  
Para uma sequência de comprimento 1 existem duas opções: {vermelha} ou {branca}. Portanto, o número de sequências válidas é 2.

Caso de teste 2: \(n=2, m=2\).  
Como \(m \ge 2\), não há restrição efetiva para \(n=2\) além de que cada posição pode ser vermelha ou branca. Assim todas as \(2^2 = 4\) sequências são válidas.\end{ProblemaAutor}
\end{document}