Задачі
Единицы
Единицы
Рассмотрим всевозможные строки, состоящие из n символов – нулей и единиц (всего имеется 2n
таких строк). Нас интересуют те из них, в которых где-нибудь встречается отрезок из k подряд идущих единиц. Точнее, нас интересует количество таких строк. Это количество может быть довольно большим, поэтому следует выводить остаток от деления этого количества на 1000007
.
Входные данные
Два натуральных числа n и k (1 ≤ n ≤ 100000, 1 ≤ k ≤ 100).
Выходные данные
Выведите остаток от деления на 1000007 количества строк, в которых встречается хотя бы один отрезок из k подряд идущих единиц.
Вхідні дані #1
3 2
Вихідні дані #1
3
Вхідні дані #2
5 1
Вихідні дані #2
31
Вхідні дані #3
7 10
Вихідні дані #3
0