За даними натуральним \(n\) та \(k\) визначте кількість послідовностей довжини \(n\) із 0 та 1, що не містять \(k\) однакових символів поспіль. \(n≤10^6\), \(2≤k≤n+1\).

Гарантується, що відповідь не перевищує \(2^{31}-1\).

Формат вхідних даних

Вводяться два натуральні числа \(n\) і \(k\).

Формат вихідних даних

Виведіть відповідь на завдання.

Приклад вхідних даних

3 3

Приклад вихідних даних

6

Приклад вхідних даних

100 2

Приклад вихідних даних

2