E. Степени двойки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Найдите количество способов разложить число n на сумму слагаемых, являющимися степенями числа 2 (1, 2, 4, 8 и т.д.).

Способы, отличающиеся порядком слагаемых, считаются одинаковыми. Каждое число в разложении можно использовать не более k раз. Так как ответ может быть слишком большим, выведите его остаток от деления на число 109 + 7.

Входные данные

В единственной строке ввода содержатся два целых числа n и k (1 ≤ n ≤ 1018; 1 ≤ k ≤ 500).

Выходные данные

Выведите остаток от деления количества способов на 109 + 7.

Примеры
Входные данные
6 1
Выходные данные
1
Входные данные
5 2
Выходные данные
2
Входные данные
4 3
Выходные данные
3
Примечание

6 = 2 + 4

5 = 1 + 4 = 1 + 2 + 2

4 = 1 + 1 + 2 = 2 + 2 = 4