{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eRandal 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?\u003cbr\u003eThere is one $n$-dimensional hypercubic subspace that he wants to cover by the minimal number of fireflies. The side lengths of the space are $p_1, p_2, \\cdots, p_n$, which means this space can be formed into $\\prod_{i \u003d 1}^{n}{p_i}$ hypercubic units.\u003cbr\u003eOne 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 $(x_1, x_2, \\cdots, x_n)$ with $1 \\leq x_i \\leq p_i$ $(i \u003d 1, 2, \\cdots, n)$, it can move to another coordinate $(y_1, y_2, \\cdots, y_n)$ if $1 \\leq x_i \\leq y_i \\leq p_i$ $(i \u003d 1, 2, \\cdots, n)$ and $\\sum_{i \u003d 1}^{n}{|x_i - y_i|} \u003d 1$. 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.\u003cbr\u003eYour task is to determine the minimum number of fireflies that should be involved and print the answer in modulo $(10^9 + 7)$.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains one integer $T$, indicating the number of test cases.\u003cbr\u003eThe following lines describe all the test cases. For each test case:\u003cbr\u003eThe first line contains one integer $n$, indicating the dimension of the space.\u003cbr\u003eThe second line contains $n$ space-separated integers, indicating the side lengths of the space.\u003cbr\u003e$1 \\leq T \\leq 2000$, $1 \\leq n \\leq 32$, $1 \\leq p_i \\leq 10^9$ $(i \u003d 1, 2, \\cdots, n)$.\u003cbr\u003eIt is guaranteed that no more than $200$ test cases satisfy $n \u0026gt; 8$, no more than $20$ test cases satisfy $n \u0026gt; 16$ and no more than $2$ test cases satisfy $n \u0026gt; 24$.\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"For each test case, print the answer modulo $(10^9 + 7)$ in one line.\u003cbr\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n1\r\n10\r\n2\r\n3 4\r\n3\r\n3 3 3\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n3\r\n7\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cbr\u003eFor the first sample, one firefly could cover all the units.\u003cbr\u003eFor the second sample, one possible best way is that each firefly covers all the units with the same second coordinate, which involves three fireflies.\u003cbr\u003e"}}]}