Bits 2

 

Duas sequências de $N$ bits são distintas se, para alguma posição $i$, $1\leq i\leq N$, o bit na posição $i$ de uma sequência é distinto no 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:

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$ ($1 \leq N \leq 10^5$) e $K$ ($1\leq K\leq N+1$).

Saída