ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Лучше поздно, чем никогда

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

B. Ипотека в Тридевятом Царстве

Ограничение времени: 3.0 секунды
Ограничение памяти: 128 МБ
В Тридевятом Царстве ходят монеты номиналом в 1 золотой, k золотых, k2 золотых, k3 золотых и так далее. Иван-Дурак взял у Кощея Бессмертного ипотеку на новую избу и платит теперь по ней каждый месяц ровно n золотых. Сколько существует различных наборов из l монет, которыми можно уплатить n золотых без сдачи? Порядок монет в наборе значения не имеет.

Исходные данные

В первой строке записано целое число t — количество тестов (1 ≤ t ≤ 100). Каждая из следующих t строк содержит целые числа n, k, l (1 ≤ n ≤ 1018; 2 ≤ k ≤ 1018; 1 ≤ l ≤ 100).

Результат

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

Пример

исходные данныерезультат
3
12 3 4
7 2 5
7 2 2
2
1
0

Замечания

В первом примере 12 золотых можно уплатить четырьмя монетами в 3 золотых или одной монетой в 9 золотых и тремя монетами в 1 золотой. Во втором примере 7 золотых можно уплатить только тремя монетами в 1 золотой и двумя монетами в 2 золотых. В третьем примере ни одного подходящего набора не существует, т.к. для уплаты 7 золотых нужно не менее трёх монет.
Автор задачи: Даниил Айзенштейн, подготовка — Олег Меркурьев
Источник задачи: Контест "Лучше поздно, чем никогда"
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 2129. Ипотека в Тридевятом Царстве