Very stupid question, but are all the elements distinct? Then it could be easier. With duplicates, it won't. Even counting the possible nice permutatiosn would be difficult then.

I could thought of a solution of n*2^n...

if you choose an element as starting point and then do recursion to choose the -1 or +1 (if exists) then keep a sum tracker go on with it.

Then it may be solvable for n<=12

Also starting point are distinct so , if there are multpile same numbers we only have to choose the distinct ones.

Okay, Jason, here's the solution for only distinct elements array in block form:

def solve(array):
    array.sort()
    the_one_having_nice_subarrays = []
    the_nice_subarrays = []

    for i in range(len(array) - 1):
        the_nice_subarrays.append(array[i])
        if array[i + 1] != array[i] + 1:
            the_one_having_nice_subarrays.append(the_nice_subarrays)
            the_nice_subarrays = []
    the_nice_subarrays.append(array[-1])
    the_one_having_nice_subarrays.append(the_nice_subarrays)

    MOD = 10 ** 9 + 7
    total_sum = 0

    for a_list in the_one_having_nice_subarrays:
        t = len(a_list)
        if t == 0:
            continue
        A = a_list[0]

        t2 = t * t
        t3 = t2 * t
        t4 = t3 * t

        term = (
            2 * t4
            + 4 * A * t3
            + 4 * t3
            + 12 * A * t2
            - 8 * t2
            - 4 * A * t
            + 2 * t
        ) // 12

        term %= MOD
        total_sum = (total_sum + term) % MOD

    return total_sum

Isn't this O(n log n)? And also, did the format myself this time. The formula is the large one which is spread over multiple lines for better vision.

The problem has a solution.