{"raw_statement":[{"iden":"statement","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"},{"iden":"входные данные","content":"В первой строке дано целое число T – количество тестов, 1 ≤ T ≤ 105.В следующих T строках через пробел даны по два целых числа 1 ≤ n ≤ 105 и 1 ≤ k ≤ 109."},{"iden":"выходные данные","content":"Для каждого теста в отдельной строке выведите одно целое число – искомое количество множеств по модулю 109 + 7."},{"iden":"пример","content":"Входные данные410 410 110 104 3Выходные данные41101"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**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.","simple_statement":"Given a line of n regions, each has either a tree (height > 0) or a water source (height = 0).  \nWater spreads left and right from each water source until it hits a tree with height ≥ H or the edge.  \nA region is wet if water reaches it.  \n\nFor each query (L, R, H), check if at least one region between L and R (inclusive) is wet.  \nPrint \"Yes\" if yes, \"No\" otherwise.","has_page_source":false}