Задача №113998. Число множеств с разделенными элементами
Вам даны два числа n и k . Назовем подмножество A множества {1, ..., n } хорошим, если любые два различные элемента A различаются не менее, чем на k . Найдите количество хороших множеств максимальной мощности. Так как ответ может быть достаточно большим, выведите его по модулю 10 9 + 7 .
В первой строке дано целое число T – количество тестов, 1 ≤ T ≤ 10 5 .
В следующих T строках через пробел даны по два целых числа 1 ≤ n ≤ 10 5 и 1 ≤ k ≤ 10 9 .
Для каждого теста в отдельной строке выведите одно целое число – искомое количество множеств по модулю 10 9 + 7 .
Подзадача 1 (30 баллов): \(T = 1, n \le 20, k \le 20\).
Подзадача 2 (15 баллов): \(k \le 2\).
Подзадача 3 (55 баллов): нет доп. ограничений.
4 10 4 10 1 10 10 4 3
4 1 10 1