Задача №2997. Последовательности из 0 и 1 без k одинаковых символов подряд
По данным натуральным n и k определите количество последовательностей длины n из 0 и 1, не содержащих k одинаковых символов подряд. n≤106, 2≤k≤n+1. Гарантируется, что ответ не превосходит 231-1.
Входные данные
Вводятся два натуральных числа n и k.
Выходные данные
Выведите ответ на задачу.
Примеры
Входные данные
3 3
Выходные данные
6
Входные данные
100 2
Выходные данные
2
Сдать: для сдачи задач необходимо войти в систему