{"problem":{"name":"H. Число множеств с разделенными элементами","description":{"content":"Вам даны два числа n и k. Назовем подмножество A множества {1, ..., n} хорошим, если любые два различные элемента A различаются не менее, чем на k. Найдите количество хороших множеств максимальной мощ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10144H"},"statements":[{"statement_type":"Markdown","content":"Вам даны два числа n и k. Назовем подмножество A множества {1, ..., n} хорошим, если любые два различные элемента A различаются не менее, чем на k. Найдите количество хороших множеств максимальной мощности. Так как ответ может быть достаточно большим, выведите его по модулю 109 + 7.\n\nВ первой строке дано целое число T – количество тестов, 1 ≤ T ≤ 105.\n\nВ следующих T строках через пробел даны по два целых числа 1 ≤ n ≤ 105 и 1 ≤ k ≤ 109.\n\nДля каждого теста в отдельной строке выведите одно целое число – искомое количество множеств по модулю 109 + 7.\n\n## Входные Данные\n\nВ первой строке дано целое число T – количество тестов, 1 ≤ T ≤ 105.В следующих T строках через пробел даны по два целых числа 1 ≤ n ≤ 105 и 1 ≤ k ≤ 109.\n\n## Выходные Данные\n\nДля каждого теста в отдельной строке выведите одно целое число – искомое количество множеств по модулю 109 + 7.\n\n## Пример\n\nВходные данные410 410 110 104 3Выходные данные41101\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ denote the number of regions and queries, respectively.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence where $ a_i \\in \\mathbb{Z}_{\\geq 0} $:  \n- $ a_i = 0 $ indicates a water source at region $ i $,  \n- $ a_i > 0 $ indicates a tree of height $ a_i $ at region $ i $.  \n\nLet $ W = \\{ i \\in \\{1, \\dots, n\\} \\mid a_i = 0 \\} $ be the set of water source positions.  \n\nFor a given water level $ H \\geq 0 $, define the *flooded region* from a water source at position $ i $ as the maximal contiguous interval $ [l_i, r_i] $ such that:  \n- $ l_i = \\min \\{ j \\in \\{1, \\dots, i\\} \\mid \\forall k \\in [j, i-1],\\ a_k < H \\} \\cup \\{1\\} $,  \n- $ r_i = \\max \\{ j \\in \\{i, \\dots, n\\} \\mid \\forall k \\in [i+1, j],\\ a_k < H \\} \\cup \\{n\\} $.  \n\nDefine the *wet region set* under water level $ H $ as:  \n$$\nF(H) = \\bigcup_{i \\in W} [l_i, r_i]\n$$\n\n**Constraints**  \n1. $ 1 \\leq n, m \\leq 10^6 $  \n2. $ 0 \\leq a_i \\leq 10^9 $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. For each query: $ 1 \\leq L \\leq R \\leq n $, $ 0 \\leq H \\leq 10^9 $\n\n**Objective**  \nFor each query $ (L, R, H) $, determine:  \n$$\n\\text{Is } F(H) \\cap [L, R] \\neq \\emptyset \\text{?}\n$$  \nOutput \"Yes\" if true, \"No\" otherwise.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10144H","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}