{"problem":{"name":"F. Fireflies","description":{"content":"Randal is a master of high-dimensional space. All the species living in his space are regarded as fireflies for him. One day he came up with a problem but failed to solve it. Are you the one who can s","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10211F"},"statements":[{"statement_type":"Markdown","content":"Randal is a master of high-dimensional space. All the species living in his space are regarded as fireflies for him. One day he came up with a problem but failed to solve it. Are you the one who can solve that?\n\nThere is one n-dimensional hypercubic subspace that he wants to cover by the minimal number of fireflies. The side lengths of the space are p1, p2, ..., pn, which means this space can be formed into  hypercubic units.\n\nOne unit is considered as covered if there exists a firefly that has visited it. Each firefly is able to cover several units through its own traveling. Assuming a firefly is located at the coordinate (x1, x2, ..., xn) with 1 ≤ xi ≤ pi (i = 1, 2, ..., n), it can move to another coordinate (y1, y2, ..., yn) if 1 ≤ xi ≤ yi ≤ pi (i = 1, 2, ..., n) and . In addition, The travel of one firefly can start or end at any location and might have any times of moves but one firefly could only travel once.\n\nYour task is to determine the minimum number of fireflies that should be involved and print the answer in modulo (109 + 7).\n\nThe first line contains one integer T, indicating the number of test cases.\n\nThe following lines describe all the test cases. For each test case:\n\nThe first line contains one integer n, indicating the dimension of the space.\n\nThe second line contains n space-separated integers, indicating the side lengths of the space.\n\n1 ≤ T ≤ 2000, 1 ≤ n ≤ 32, 1 ≤ pi ≤ 109 (i = 1, 2, ..., n).\n\nIt is guaranteed that no more than 200 test cases satisfy n > 8, no more than 20 test cases satisfy n > 16 and no more than 2 test cases satisfy n > 24.\n\nFor each test case, print the answer modulo (109 + 7) in one line.\n\nFor the first sample, one firefly could cover all the units.\n\nFor the second sample, one possible best way is that each firefly covers all the units with the same second coordinate, which involves three fireflies.\n\n## Input\n\nThe first line contains one integer T, indicating the number of test cases.The following lines describe all the test cases. For each test case:The first line contains one integer n, indicating the dimension of the space.The second line contains n space-separated integers, indicating the side lengths of the space.1 ≤ T ≤ 2000, 1 ≤ n ≤ 32, 1 ≤ pi ≤ 109 (i = 1, 2, ..., n).It is guaranteed that no more than 200 test cases satisfy n > 8, no more than 20 test cases satisfy n > 16 and no more than 2 test cases satisfy n > 24.\n\n## Output\n\nFor each test case, print the answer modulo (109 + 7) in one line.\n\n[samples]\n\n## Note\n\nFor the first sample, one firefly could cover all the units.For the second sample, one possible best way is that each firefly covers all the units with the same second coordinate, which involves three fireflies.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the dimension of the hypercubic space.  \nLet $ \\mathbf{p} = (p_1, p_2, \\dots, p_n) \\in \\mathbb{Z}^n $ with $ p_i \\geq 1 $ be the side lengths.  \nThe space consists of all integer points $ \\mathbf{x} = (x_1, \\dots, x_n) $ with $ 1 \\leq x_i \\leq p_i $.  \n\nA firefly starting at $ \\mathbf{x} $ can move to $ \\mathbf{y} $ if $ x_i \\leq y_i \\leq p_i $ for all $ i $, i.e., it can only move in the positive direction in each coordinate (monotonic path).  \nEach firefly performs exactly one such monotonic path (possibly of length 0).  \n\n**Constraints**  \n1. $ 1 \\leq T \\leq 2000 $  \n2. $ 1 \\leq n \\leq 32 $  \n3. $ 1 \\leq p_i \\leq 10^9 $ for all $ i \\in \\{1, \\dots, n\\} $  \n4. At most 200 test cases have $ n > 8 $, at most 20 have $ n > 16 $, at most 2 have $ n > 24 $.  \n\n**Objective**  \nFind the minimum number of monotonic paths (fireflies) needed to cover all points in the grid $ [1, p_1] \\times \\cdots \\times [1, p_n] $.  \nOutput the answer modulo $ 10^9 + 7 $.  \n\n**Key Insight**  \nThis is equivalent to finding the minimum number of chains (under the partial order $ \\mathbf{x} \\leq \\mathbf{y} $) that cover the poset $ \\prod_{i=1}^n [1, p_i] $.  \nBy Dilworth’s theorem, this equals the size of the largest antichain.  \n\nIn the grid poset $ \\prod_{i=1}^n [1, p_i] $, the largest antichain is the set of points with coordinate sum equal to the median value, i.e.,  \n$$\n\\max_{k} \\left| \\left\\{ \\mathbf{x} \\in \\prod_{i=1}^n [1, p_i] : \\sum_{i=1}^n x_i = k \\right\\} \\right|\n$$  \nThis is the maximum number of points with the same rank (same sum), and equals the coefficient of $ x^m $ in the generating function  \n$$\n\\prod_{i=1}^n (x + x^2 + \\cdots + x^{p_i})\n$$  \nwhere $ m = \\left\\lfloor \\frac{1}{2} \\left( \\sum_{i=1}^n p_i + n \\right) \\right\\rfloor $ (the middle rank).  \n\nThus, the minimal number of fireflies is:  \n$$\n\\boxed{ \\max_{k} \\left[ x^k \\right] \\prod_{i=1}^n \\left( \\frac{x - x^{p_i + 1}}{1 - x} \\right) }\n$$  \ncomputed modulo $ 10^9 + 7 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10211F","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}