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