{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eCSL loves stone games. He has $n$ stones; each has a weight $a_i$. CSL wants to get some stones. The rule is that the pile he gets should have a higher or equal total weight than the rest; however if he removes any stone in the pile he gets, the total weight of the pile he gets will be no higher than the rest. It\u0027s so easy for CSL, because CSL is a talented stone-gamer, who can win almost every stone game! So he wants to know the number of possible plans. The answer may be large, so you should tell CSL the answer modulo $10^9 + 7$.\u003c/p\u003e\n\u003cp\u003eFormerly, you are given a labelled multiset $S\u003d\\{a_1,a_2,\\ldots,a_n\\}$, find the number of subsets of $S$: $S\u0027\u003d\\{a_{i_1}, a_{i_2}, \\ldots, a_{i_k} \\}$, such that $$\\left(Sum(S\u0027) \\ge Sum(S-S\u0027) \\right) \\land \\left(\\forall t \\in S\u0027, Sum(S\u0027) - t \\le Sum(S-S\u0027) \\right) .$$\u003c/p\u003e\n\u003ch3\u003eInputFile\u003c/h3\u003e\n\u003cp\u003eThe first line an integer $T$ ($1 \\leq T \\leq 10)$, which is the number of cases.\u003c/p\u003e\n\u003cp\u003eFor each test case, the first line is an integer $n$ ($1 \\leq n \\leq 300$), which means the number of stones. The second line are $n$ space-separated integers $a_1,a_2,\\ldots,a_n$ ($1 \\leq a_i \\leq 500$).\u003c/p\u003e\n\u003ch3\u003eOutputFile\u003c/h3\u003e\n\u003cp\u003eFor each case, a line of only one integer $t$ --- the number of possible plans. If the answer is too large, please output the answer modulo $10^9 + 7$.\u003c/p\u003e"}},{"title":"Sample 1","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\n3\n1 2 2\n3\n1 2 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr /\u003e\u003cp\u003eIn example 1, CSL can choose the stone 1 and 2 or stone 1 and 3.\u0026nbsp;\u003c/p\u003e\u003cp\u003e\u0026nbsp;In example 2, CSL can choose the stone 3.\u003c/p\u003e"}}]}