Одиниці

Розгляньмо всі можливі рядки довжини n, що складаються з нулів і одиниць (усього таких рядків 2^n). Нас цікавлять ті з них, у яких є хоча б один відрізок з k підряд ідучих одиниць. Завдання полягає в тому, щоб знайти кількість таких рядків. Оскільки це число може бути дуже великим, потрібно вивести залишок від ділення цього числа на 1000007.

Вхідні дані

Два натуральних числа n і k (1 ≤ n ≤ 100000, 1 ≤ k ≤ 100).

Вихідні дані

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

Приклади