XXVI Olimpíada Brasileira de Informática
Submeta sua solução

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 109+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
	

 

Tarefas Programação Nível 1
Promoção
logo sbc
Patrocínio
Apoio
Coordenação