子序列之和

【题目描述】

给定一个长度为 $n$ 的正整数序列 $a_1,a_2,\ldots,a_n$。

一个子序列可以通过从原序列中删除若干个元素，并保持剩余元素的相对顺序得到。空子序列也被计入，它的元素和为 $0$。

现在，请你求出所有子序列的元素和之和，并将答案对 $10^9+7$ 取模。

本题包含多组测试数据。

---

【输入描述】

第一行输入一个正整数 $T$，表示测试数据组数。

接下来依次输入 $T$ 组测试数据。对于每组测试数据：

第一行输入一个正整数 $n$。

第二行输入 $n$ 个正整数 $a_1,a_2,\ldots,a_n$。

保证：

• $1\le T\le 10$；
• $1\le n\le 2\times 10^5$；
• $1\le a_i\le 10^9$；
• 单个测试点内所有测试数据的 $n$ 之和不超过 $2\times 10^5$。

---

【输出描述】

对于每组测试数据，输出一行一个整数，表示所有子序列的元素和之和对 $10^9+7$ 取模后的结果。

---

【样例 1】

【样例 1 输入】

1
3
1 2 3

【样例 1 输出】

24

【样例 1 解释】

所有子序列的元素和分别为：

$$0,1,2,3,1+2,1+3,2+3,1+2+3.$$

它们的总和为 $24$。

---

【样例 2】

【样例 2 输入】

1
4
1 1 1 1

【样例 2 输出】

32

【样例 2 解释】

每个 $1$ 都会出现在 $2^3=8$ 个子序列中，因此答案为 $4\times 8=32$。

---

【样例 3】

见选手目录下的 Data/sample3.in 和 Data/sample3.ans。

该样例满足每组测试数据 $n\le 10$。

---

【样例 4】

见选手目录下的 Data/sample4.in 和 Data/sample4.ans。

该样例满足每组测试数据 $n\le 1000$。

---

【样例 5】

见选手目录下的 Data/sample5.in 和 Data/sample5.ans。

该样例满足每组测试数据 $n\le 1000$。

---

【样例 6】

见选手目录下的 Data/sample6.in 和 Data/sample6.ans。

该样例无特殊性质。

---

【数据规模与约定】

测试点编号	分数	特殊性质
1 ~ 4	20	每组测试数据 $n\le 10$
5 ~ 8		每组测试数据 $n\le 20$
9 ~ 12		每组测试数据 $n\le 1000$
13 ~ 20	40	无

点击下载本题选手目录