### 问题描述 麻衣是蓝桥的一名数据科学家，她每天都要处理大量的数据。有一天，她发现了一个有趣的问题，对于小规模的数据这个问题非常容易解决，但随着数据点数量的增加，问题的复杂性也在增加。因此，麻衣需要你的帮助来解决这个问题。 给定一个集合 $S$，它包含 $N$ 个非负整数（集合中的某些整数可能会出现多次），你需要找出 $f(S)$ 的值。 这里 $f(S)$ 的定义如下： $$ f(S) = \sum\limits_{s \in subsets(S)} \max(s) - \min(s) $$ 其中 $subsets(S)$ 表示集合 $S$ 的所有子集，$\max(s)$ 和 $\min(s)$ 分别表示子集 $s$ 中的最大值和最小值。因为 $f(S)$ 的值可能非常大，所以请你输出 $f(S)$ 对 $10^9 + 7$ 取模后的结果。 注意，集合 $S$ 中可能包含重复的值。例如，对于集合 $S$ = { $1,2,2$ }，我们认为第一个 $2$ 和第二个 $2$ 是不同的，所以会有两个不同的子集 { $1,2$ }。 ### 输入格式 第一行包含一个整数 $N$，表示集合 $S$ 的元素数量。第二行包含 $N$ 个用空格隔开的非负整数，表示集合 $S$ 的元素。 数据范围保证：$1 \leq N \leq 10^5$，$1 \leq S_i \leq 10^9$。 ### 输出格式 输出一个整数，表示对应的 $f(S)$ 对 $10^9 + 7$ 取模后的结果。 ### 样例输入 ```text 3 1 2 3 ``` ### 样例输出 ```text 6 ``` ### 说明 对于测试样例，可以找出的子集和对应的 $\max(s) - \min(s)$ 值如下： - 子集 { $1$ }，$\max(s) - \min(s) = 0$。 - 子集 { $2$ }，$\max(s) - \min(s) = 0$。 - 子集 { $3$ }，$\max(s) - \min(s) = 0$。 - 子集 { $1,2$ }，$\max(s) - \min(s) = 1$。 - 子集 { $2,3$ }，$\max(s) - \min(s) = 1$。 - 子集 { $1,3$ }，$\max(s) - \min(s) = 2$。 - 子集 { $1,2,3$ }，$\max(s) - \min(s) = 2$。 所以 $f(S)$ 的值为 $0 + 0 + 0 + 1 + 1 + 2 + 2 = 6$。