Məsələlər
Единицы
Единицы
Рассмотрим всевозможные строки, состоящие из n символов – нулей и единиц (всего имеется 2n
таких строк). Нас интересуют те из них, в которых где-нибудь встречается отрезок из k подряд идущих единиц. Точнее, нас интересует количество таких строк. Это количество может быть довольно большим, поэтому следует выводить остаток от деления этого количества на 1000007
.
Входные данные
Два натуральных числа n и k (1 ≤ n ≤ 100000, 1 ≤ k ≤ 100).
Выходные данные
Выведите остаток от деления на 1000007 количества строк, в которых встречается хотя бы один отрезок из k подряд идущих единиц.
Giriş verilənləri #1
3 2
Çıxış verilənləri #1
3
Giriş verilənləri #2
5 1
Çıxış verilənləri #2
31
Giriş verilənləri #3
7 10
Çıxış verilənləri #3
0