Approach

Let ~I_i~ be the indicator that values ~i~ and ~i + 1~ occupy adjacent positions in the permutation. The total score is

~X = \sum_{i=1}^{n-1} w_i I_i~.

By linearity,

~E[X] = \sum_{i=1}^{n-1} w_i \Pr(I_i = 1)~.

To compute the probability, glue ~i~ and ~i + 1~ into a single block. The block may be ordered in ~2~ ways, and the remaining ~n - 1~ objects (the block plus ~n - 2~ other values) may be permuted freely, so

~\Pr(I_i = 1) = \frac{2 \cdot (n - 1)!}{n!} = \frac{2}{n}~.

A common mistake is to answer ~2/(n - 1)~: after placing ~i~, two of the remaining ~n - 1~ slots look adjacent, but that count is wrong at the two endpoints of the array, where ~i~ has only one neighbour slot. Averaging over the position of ~i~ recovers ~2/n~.

Therefore

~E[X] = \frac{2}{n} \sum_{i=1}^{n-1} w_i~.

The indicators are dependent (overlapping pairs cannot all be adjacent at once in general), but linearity still applies. The implementation is ~O(n)~.

Solution (C++)

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1000000007;

long long modpow(long long a, long long e) {
    long long r = 1;
    a %= MOD;
    while (e) {
        if (e & 1) {
            r = r * a % MOD;
        }
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    if (n == 1) {
        cout << 0 << "\n";
        return 0;
    }
    long long sum = 0;
    for (int i = 0; i < n - 1; i++) {
        long long w;
        cin >> w;
        sum += w;
        if (sum >= MOD) {
            sum %= MOD;
        }
    }
    sum %= MOD;
    cout << 2 * sum % MOD * modpow(n, MOD - 2) % MOD << "\n";
}