의사 난수

숫자가 진짜 무작위라면 길이 $n$인 모든 비트열(0과 1로 이루어진 문자열)이 같은 확률로 나타나야 한다. 예를 들어 111111과 010110이 나올 확률은 같아야 한다. 하지만 대부분의 사람은 같은 비트가 계속 반복해서 보이면 그 과정이 진짜 무작위일 수 없다고 생각한다.

당신은 비디오 게임에 쓸 길이 $n$인 무작위 비트열을 만드는 일을 맡았다. 게임 제작자는 0 또는 1이 연속으로 $k$개를 초과하여 나오는 비트열을 모두 제외해 달라고 요청했다. 예를 들어 $n = 4$, $k = 2$이면 유효한 비트열은 0010, 0011, 0100, 0101, 0110, 1001, 1010, 1011, 1100, 1101의 10개다. 나머지 6개는 같은 비트가 3번 이상 연속으로 나오므로 유효하지 않다.

$n$과 $k$가 주어졌을 때, 0 또는 1이 $k$보다 길게 연속으로 나오는 구간이 없는 길이 $n$의 비트열 개수를 구하라.

입력은 한 줄이며, 두 정수 $n$($2 \le n \le 20$)과 $k$($1 \le k \le n$)이 주어진다. $n$은 비트열의 길이이고, $k$는 비트열에서 0 또는 1이 연속으로 나올 수 있는 최대 길이이다.

같은 비트가 $k$보다 길게 연속으로 나오지 않는, 길이 $n$의 유효한 비트열의 개수를 출력한다.