{"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\"\u003eYou have a tree on $n$ vertices, and each vertex has a weight $a_v$ and a degree at most $5$.\u003cbr\u003e\u003cbr\u003eLet\u0027s call the \u003cb\u003edensity\u003c/b\u003e of a subset of vertices $S$ value $\\frac{\\sum_{v \\in S} a_v}{|S|}$, and call the \u003cb\u003ebeauty\u003c/b\u003e of the tree with some vertices turned off the maximum value of the \u003cb\u003edensity\u003c/b\u003e of a subset of at least two turned on vertices with connected induced subgraph, or $0$ if no such subset exists.\u003cbr\u003e\u003cbr\u003eNow you need to calculate the number of ways to choose such a set of turned off vertices among $2^n$ ways that the \u003cb\u003ebeauty\u003c/b\u003e of the tree is no larger than $x$, modulo $1\\,000\\,000\\,007$.\u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The input contains several test cases, and the first line contains a single integer $T~(1 \\le T \\le 30)$, the number of test cases.\u003cbr\u003e\u003cbr\u003eThe first line of each test case contains two integers $n~(2 \\leq n \\leq 35\\,000)$ and $x~(0 \\leq x \\leq 35\\,000)$, the number of vertices of a tree and the constraint on the beauty.\u003cbr\u003e\u003cbr\u003eThe next line contains $n$ integers $a_1, a_2, \\ldots, a_n~(0 \\leq a_i \\leq 35\\,000)$, the weights of the tree vertices.\u003cbr\u003e\u003cbr\u003eEach of the next $n-1$ lines contains two integers $u$ and $v~(1 \\leq u, v \\leq n)$, describing an edge connecting vertices $u$ and $v$ in the tree. \u003cbr\u003e\u003cbr\u003e\u003cb\u003eIt is guaranteed that each vertex of a tree has a degree at most $5$.\u003c/b\u003e\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"For each test case, output a line containing a single integer, indicating the number of ways to choose such a set of turned off vertices among $2^n$ ways that the \u003cb\u003ebeauty\u003c/b\u003e of the tree is no larger than $x$, modulo $1\\,000\\,000\\,007$.\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\u003e2\r\n5 0\r\n1 1 1 1 1\r\n1 2\r\n2 3\r\n3 4\r\n4 5\r\n3 2\r\n2 1 3\r\n1 2\r\n1 3\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e13\r\n6\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}