{"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\"\u003e兰德尔是高维空间的大师。在他的空间中生活的所有物种对他来说都像萤火虫一样。有一天,他想出了一个问题,但无法解决。你能解决这个问题吗?\u003cbr\u003e他想要用尽可能少的萤火虫来覆盖一个 $n$ 维超立方子空间。空间的边长为 $p_1, p_2, \\cdots, p_n$,这意味着这个空间可以被划分为 $\\prod_{i \u003d 1}^{n}{p_i}$ 个超立方体单位。\u003cbr\u003e如果存在一个访问过它的萤火虫,那么一个单位被认为是被覆盖了。每只萤火虫能够通过自己的移动覆盖多个单位。假设一只萤火虫位于坐标 $(x_1, x_2, \\cdots, x_n)$,带有 $1 \\leq x_i \\leq p_i$ $(i \u003d 1, 2, \\cdots, n)$,如果 $1 \\leq x_i \\leq y_i \\leq p_i$ $(i \u003d 1, 2, \\cdots, n)$ 且 $\\sum_{i \u003d 1}^{n}{|x_i - y_i|} \u003d 1$,它可以移动到另一个坐标 $(y_1, y_2, \\cdots, y_n)$。此外,一只萤火虫的移动可以从任何位置开始或结束,可能有任意次移动,但一只萤火虫只能移动一次。\u003cbr\u003e你的任务是确定应该涉及的最小萤火虫数量,并以模 $(10^9 + 7)$ 的形式打印答案。\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"第一行包含一个整数 $T$,表示测试用例的数量。\u003cbr\u003e以下行描述所有测试用例。对于每个测试用例:\u003cbr\u003e第一行包含一个整数 $n$,表示空间的维数。\u003cbr\u003e第二行包含 $n$ 个以空格分隔的整数,表示空间的边长。\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\u003e保证不会有超过 $200$ 个测试用例满足 $n \u0026gt; 8$,不会有超过 $20$ 个测试用例满足 $n \u0026gt; 16$,也不会有超过 $2$ 个测试用例满足 $n \u0026gt; 24$。\u003cbr\u003e"}},{"title":"输出","value":{"format":"HTML","content":"对于每个测试用例,以一行的形式打印答案模 $(10^9 + 7)$。\u003cbr\u003e"}},{"title":"示例","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"}},{"title":"提示","value":{"format":"HTML","content":"\u003cbr\u003e对于第一个示例,一只萤火虫可以覆盖所有单位。\u003cbr\u003e对于第二个示例,一个可能的最佳方法是每只萤火虫覆盖所有具有相同第二坐标的单位,这涉及到三只萤火虫。\u003cbr\u003e"}}]}