404184: GYM101445 H Число множеств с разделенными элементами

H. Число множеств с разделенными элементамиограничение по времени на тест2 секундыограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Вам даны два числа n и k. Назовем подмножество A множества {1, ..., n} хорошим, если любые два различные элемента A различаются не менее, чем на k. Найдите количество хороших множеств максимальной мощности. Так как ответ может быть достаточно большим, выведите его по модулю 10⁹ + 7.

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

В первой строке дано целое число T – количество тестов, 1 ≤ T ≤ 10⁵.

В следующих T строках через пробел даны по два целых числа 1 ≤ n ≤ 10⁵ и 1 ≤ k ≤ 10⁹.

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

Для каждого теста в отдельной строке выведите одно целое число – искомое количество множеств по модулю 10⁹ + 7.

ПримерВходные данные

4
10 4
10 1
10 10
4 3

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

4
1
10
1