P16617 [GKS 2017 #B] Math Encoder

Math 教授正在从事一个秘密项目，面临一个挑战：需要将一组数字以最有效的方式编码成一个数字。经过大量研究，Math 教授发现了一个三步过程，可以最好地对这些数字进行编码： 1. 第一步，找出数字列表的所有非空子集，然后对每个子集，求出该子集中最大值与最小值的差（即最大值减去最小值）。注意，如果子集中只有一个数字，则该数字既是最大值也是最小值。整个集合本身也被视为一个子集。 2. 然后，将所有差值相加，得到最终的编码数字。 3. 由于数字可能很大，请输出该数字对 $10^9 + 7$（$1000000007$）取模的结果。 教授分享了一个例子及其解释如下。给定一个数字列表，你能帮助教授构建一个高效的函数来计算最终的编码数字吗？

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例，每个测试用例由两行定义： 1. 第一行给出一个正整数 $N$，表示列表中数字的个数。 2. 第二行包含 $N$ 个正整数 $K_i$，按非递减顺序排列。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是最终的编码数字。 由于输出可能非常大，我们只要求输出结果除以素数 $10^9 + 7$（$1000000007$）的余数。

**样例输入的解释** 1. 找出所有子集并计算最大值与最小值的差： - [$3$]，最大值 $-$ 最小值 $= 3 - 3 = 0$。 - [$6$]，最大值 $-$ 最小值 $= 6 - 6 = 0$。 - [$7$]，最大值 $-$ 最小值 $= 7 - 7 = 0$。 - [$9$]，最大值 $-$ 最小值 $= 9 - 9 = 0$。 - [$3, 6$]，最大值 $-$ 最小值 $= 6 - 3 = 3$。 - [$3, 7$]，最大值 $-$ 最小值 $= 7 - 3 = 4$。 - [$3, 9$]，最大值 $-$ 最小值 $= 9 - 3 = 6$。 - [$6, 7$]，最大值 $-$ 最小值 $= 7 - 6 = 1$。 - [$6, 9$]，最大值 $-$ 最小值 $= 9 - 6 = 3$。 - [$7, 9$]，最大值 $-$ 最小值 $= 9 - 7 = 2$。 - [$3, 6, 7$]，最大值 $-$ 最小值 $= 7 - 3 = 4$。 - [$3, 6, 9$]，最大值 $-$ 最小值 $= 9 - 3 = 6$。 - [$3, 7, 9$]，最大值 $-$ 最小值 $= 9 - 3 = 6$。 - [$6, 7, 9$]，最大值 $-$ 最小值 $= 9 - 6 = 3$。 - [$3, 6, 7, 9$]，最大值 $-$ 最小值 $= 9 - 3 = 6$。 2. 将上一步计算出的差值求和： $$3 + 4 + 6 + 1 + 3 + 2 + 4 + 6 + 6 + 3 + 6$$ $$= 44$$ 3. 求答案对 $10^9 + 7$（$1000000007$）取模的结果： $44 \bmod 1000000007 = 44$ ### 限制条件 $1 \le T \le 25$。 对于所有 $i$，$1 \le K_i \le 10000$。 对于所有 $i < N-1$，$K_i \le K_{i+1}$。 **小数据集（测试集 1 – 可见）** $1 \le N \le 10$。 **大数据集（测试集 2 – 隐藏）** $1 \le N \le 10000$。 翻译由 DeepSeek V4 Pro 完成