The problem goes like this:

You are given an integer array nums.

A nice permutation is defined as a permutation of any non-empty subset of nums such that the absolute difference between any two consecutive elements is exactly 1. A permutation of size 1 is considered nice by definition. A subset is any non-empty selection of elements from nums (regardless of order). A permutation of a subset is any reordering of the elements of a subset.

Your task is to compute the sum of all elements across all such nice permutations.

Since the total may be very large, output the result modulo $$$10^9 + 7$$$.

Input

• An array nums of integers.
• $$$1 \leq \text{nums.length} \leq 10^5$$$ (maybe no solution exists though ... I can't guarantee anything lol)
• $$$0 \leq \text{nums}[i] \leq 10^5$$$ (maybe no solution exists though ... I can't guarantee anything lol)

Output

• A single integer: the sum of all elements in all nice permutations of all non-empty subsets of nums, taken modulo $$$10^9 + 7$$$.

Examples

nums = [1, 2, 3]

• [1], [2], [3], [1,2], [2,1], [2,3], [3,2], [1,2,3], [3,2,1] are all valid.
• The sum is 34.
• [1, 3], [3, 1], [2,3,1], [2,1,3], [3,1,2], and [1,3,2] are not valid.

nums = [2, 3, 2]

• [2], [2], [3], [2,3], [3,2], [2,3], [3,2], [2,3,2], [2,3,2] are all valid.
• The sum is 41.
• [2,2], [2,2], [2,2,3], [2,2,3], [3,2,2], and [3,2,2] are not valid.

Apart from brute-forcing all $$$\sum_{k=1}^{n} \binom{n}{k} \cdot k!$$$ possibilities, I can't find any way to do it. I feel like we should start by sorting and making clusters (for example [1, 2, 9, 10, 11, 12] would have two clusters, [1, 2] and [9, 10, 11, 12]), but that kind of got me nowhere.