Рассмотрим всевозможные строки, состоящие из n символов – нулей и единиц (всего имеется 2n таких строк). Нас интересуют те из них, в которых где-нибудь встречается отрезок из k подряд идущих единиц. Точнее, нас интересует количество таких строк. Это количество может быть довольно большим, поэтому следует выводить остаток от деления этого количества на 1000007.

Input

Two positive integers n and k (1 ≤ n ≤ 100000, 1 ≤ k ≤ 100).

Output

Выведите остаток от деления на 1000007 количества строк, в которых встречается хотя бы один отрезок из k подряд идущих единиц.