Submeta sua solução

Arquivo:

Linguagem: Selecione C++17 / g++ C17 / gcc Javascript Java / JDK Python 3 / CPython

Submete

Nome do arquivo: bits.x, onde x deve ser c, cpp, java, js ou py

Bits

Duas sequências de N bits são distintas se, para alguma posição i, 1 ≤ i ≤ N, o bit na posição i de uma sequência é distinto do bit na posição i da outra sequência. As duas sequências de N=10 bits abaixo são distintas pois, por exemplo, os bits na posição 7, da esquerda para a direita, são distintos:

0 1 0 0 0 1 1 0 1 0
1 0 0 1 0 1 0 0 1 0 Mas veja que as duas sequências acima, apesar de distintas, têm uma característica em comum: não há três bits 1 consecutivos nelas. Neste problema, dado o número de bits N e um K, seu programa deve computar quantas sequências distintas de N bits existem, nas quais não há K bits 1 consecutivos.

Entrada

A entrada consiste de uma linha contendo os dois inteiros N e K.

Saída

Imprima uma linha contendo um inteiro, representando o número de sequências distintas de N bits, nas quais não há K bits 1 consecutivos. Porque esse número pode ser muito grande, você deve imprimir o resto da divisão dele por 10⁹+7.

Restrições

• 1 ≤ N ≤ 1000
• 1 ≤ K ≤ N+1

Informações sobre a pontuação

• Em um conjunto de casos de teste somando 20 pontos, N ≤ 20

Exemplos

Entrada 4 2

Saída 8

 

Entrada 10 3

Saída 504