SP10945 DCEPC301 - Foodie Golu

Golu 是一个超级大吃货，他希望能在聚会上尝遍所有美食。但他的妈妈担心他的体重增加，所以不同意。在争论了一番之后，他们达成了以下协议： 1. Golu 每隔 10 分钟才能吃一次。 2. 对于聚会上的摊位，他需要从一排的 $N$ 个摊位中每次选择一个摊位来吃。所选摊位必须位于剩余摊位的第 $n/2$ 或 $(n/2 + 1)$ 个位置（从 0 开始计数）。 3. 一旦选择了某个摊位，Golu 必须丢弃该摊位左边（或右边）的所有摊位，以后只能在剩下的摊位中进行选择。另外，每个摊位在整个聚会中只能被选择一次，所以选择后需要将其丢弃。 最开始，每个摊位制作食物的速度为 1 单位。Golu 发现每 10 分钟这些摊位的制作速度就会翻倍。根据每个摊位的食物种类和他的食量，他为每个摊位设定了一个值，这样他在任意时刻可以吃的食物数量就等于（摊位的值）乘以（当前的烹饪速度）。由于速度增长很快，他只记住了每个时刻速度的 $\text{speed} \mod \text{mod}$ 的结果。 为了让 Golu 吃到最多的食物，请帮他设计一个策略。 **注意：如果最后只剩下两个摊位，他必须选择其中一个摊位，并丢弃另一个。**

第一行包含一个整数 $T$，表示测试用例的数量。（$1 \le T \le 5$） 每个测试用例的第一行包含一个整数 $n$，表示聚会上的摊位数。（$1 \le n \le 3000$） 随后一行包含 $n$ 个用空格分隔的整数，表示每个摊位的值。（所有值都在 1 到 3000 之间，含端点）

对于每个测试用例，输出一行数据，表示 Golu 在该测试用例中能吃到的最大食物量对 $10^9+7$ 取模后的结果。 **本翻译由 AI 自动生成**