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

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

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

В первом примере 12 золотых можно уплатить четырьмя монетами в 3 золотых или одной монетой в 9 золотых и тремя монетами в 1 золотой. Во втором примере 7 золотых можно уплатить только тремя монетами в 1 золотой и двумя монетами в 2 золотых. В третьем примере ни одного подходящего набора не существует, т.к. для уплаты 7 золотых нужно не менее трёх монет.