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

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

Ограничение времени: 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 золотых нужно не менее трёх монет.
Автор задачи: Даниил Айзенштейн, подготовка — Олег Меркурьев