Вам даны два числа 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