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

Memory Limit:0 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

加入题单

上一题 下一题 算法标签: