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

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

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

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

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

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

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

Пример
Входные данные
4
10 4
10 1
10 10
4 3
Выходные данные
4
1
10
1