题目描述

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
4
3 6 7 9

Case #1: 44

提示

样例输入的解释

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 完成