Степени двойки
(Время: 1 сек. Память: 16 Мб Сложность: 73%)
Найдите количество способов разложить число n на сумму слагаемых, являющимися степенями числа 2 (1, 2, 4, 8 и т.д.).
Способы, отличающиеся порядком слагаемых, считаются одинаковыми. Каждое число в разложении можно использовать не более k раз. Так как ответ может быть слишком большим, выведите его остаток от деления на число 109+7.
Входные данные
Входной файл INPUT.TXT содержит два целых числа n и k (1 ≤ n ≤ 1018; 1 ≤ k ≤ 500).
Выходные данные
В выходной файл OUTPUT.TXT выведите остаток от деления количества способов на 109 + 7.
Примеры
№ | INPUT.TXT | OUTPUT.TXT |
1 | 6 1 | 1 |
2 | 5 2 | 2 |
3 | 4 3 | 3 |
Примечание
6 = 2 + 4
5 = 1 + 4 = 1 + 2 + 2
4 = 1 + 1 + 2 = 2 + 2 = 4
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|