You are given a set of n elements indexed from 1 to n. The weight of i-th element is w_{i}. The weight of some subset of a given set is denoted as $W(S) =|S|\cdot \sum_{i \in S} w_{i}$. The weight of some partition R of a given set into k subsets is $W(R) = \sum_{S \in R} W(S)$ (recall that a partition of a given set is a set of its subsets such that every element of the given set belongs to exactly one subset in partition).

Calculate the sum of weights of all partitions of a given set into exactly k non-empty subsets, and print it modulo 10^9 + 7. Two partitions are considered different iff there exist two elements x and y such that they belong to the same set in one of the partitions, and to different sets in another partition.


-----Input-----

The first line contains two integers n and k (1 ≤ k ≤ n ≤ 2·10^5) — the number of elements and the number of subsets in each partition, respectively.

The second line contains n integers w_{i} (1 ≤ w_{i} ≤ 10^9)— weights of elements of the set.


-----Output-----

Print one integer — the sum of weights of all partitions of a given set into k non-empty subsets, taken modulo 10^9 + 7.


-----Examples-----
Input
4 2
2 3 2 3

Output
160

Input
5 2
1 2 3 4 5

Output
645



-----Note-----

Possible partitions in the first sample:  {{1, 2, 3}, {4}}, W(R) = 3·(w_1 + w_2 + w_3) + 1·w_4 = 24;  {{1, 2, 4}, {3}}, W(R) = 26;  {{1, 3, 4}, {2}}, W(R) = 24;  {{1, 2}, {3, 4}}, W(R) = 2·(w_1 + w_2) + 2·(w_3 + w_4) = 20;  {{1, 3}, {2, 4}}, W(R) = 20;  {{1, 4}, {2, 3}}, W(R) = 20;  {{1}, {2, 3, 4}}, W(R) = 26; 

Possible partitions in the second sample:  {{1, 2, 3, 4}, {5}}, W(R) = 45;  {{1, 2, 3, 5}, {4}}, W(R) = 48;  {{1, 2, 4, 5}, {3}}, W(R) = 51;  {{1, 3, 4, 5}, {2}}, W(R) = 54;  {{2, 3, 4, 5}, {1}}, W(R) = 57;  {{1, 2, 3}, {4, 5}}, W(R) = 36;  {{1, 2, 4}, {3, 5}}, W(R) = 37;  {{1, 2, 5}, {3, 4}}, W(R) = 38;  {{1, 3, 4}, {2, 5}}, W(R) = 38;  {{1, 3, 5}, {2, 4}}, W(R) = 39;  {{1, 4, 5}, {2, 3}}, W(R) = 40;  {{2, 3, 4}, {1, 5}}, W(R) = 39;  {{2, 3, 5}, {1, 4}}, W(R) = 40;  {{2, 4, 5}, {1, 3}}, W(R) = 41;  {{3, 4, 5}, {1, 2}}, W(R) = 42.

Difficulty: interview

Starter code:

Solutions:
n, k = list(map(int, input().split()))

MOD = 10**9+7


def fast_modinv(up_to, M):
    ''' Fast modular inverses of 1..up_to   modulo M. '''
    modinv = [-1 for _ in range(up_to + 1)]
    modinv[1] = 1
    for x in range(2, up_to + 1):
        modinv[x] = (-(M//x) * modinv[M%x])%M
    return modinv

maxn = 2*10**5 + 10
modinv = fast_modinv(maxn, MOD)
fact, factinv = [1], [1]
for i in range(1, maxn):
    fact.append(fact[-1]*i % MOD)
    factinv.append(factinv[-1]*modinv[i] % MOD)


def Stirling(n, k):
    '''The Stirling number of second kind (number of nonempty partitions). '''
    if k > n:
        return 0
    result = 0
    for j in range(k+1):
        result += (-1 if (k-j)&1 else 1) * fact[k] * factinv[j] * factinv[k - j] * pow(j, n, MOD) % MOD
        result %= MOD
    result *= factinv[k]
    return result % MOD

W = sum(map(int, input().split())) % MOD
print((Stirling(n, k) + (n - 1) * Stirling(n - 1, k))* W % MOD)


M = 0x3b9aca07
rd = lambda: list(map(int, input().split()))
inv = lambda x: (M - M // x) * inv(M % x) % M if x - 1 else 1
n, k = rd()
w = sum(rd()) % M
modinv = [0, 1]
for i in range(2, 200005):
    modinv.append((M - M // i) * modinv[M % i] % M)
f = [1, -1] 
fa_inv = [1]
for i in range(1, 200005):
    fa_inv.append(fa_inv[-1] * modinv[i] % M)
def sti(n, m):
    r = 0
    if n >= m:
        for i in range(m + 1):
            r = (r + f[i & 1] * fa_inv[m - i] * fa_inv[i] * pow(m - i, n, M)) % M
    return r
print(w * (sti(n, k) + (n - 1) * sti(n - 1, k)) % M)


def read_data():
    n, m = map(int, list(input().strip().split()))
    a = list(map(int, list(input().strip().split())))
    return n, m, a

def get_modinv(m):
    modinv = [-1 for _ in range(m+1)]
    modinv[1] = 1
    for i in range(2,m+1):
        modinv[i] = (-(div//i) * modinv[div%i]) % div
    return modinv

def partitions(n,k):
    if k >n :
        return 0
    val = 0
    sign = 1
    if k%2 == 1:
        sign = -1
    for i in range(k+1):
        v = (fact[k] * factinv[i] * factinv[k-i] * pow(i,n,div)) % div
        val += v * sign
        val %= div
        sign *= -1
    val *= factinv[k]
    return val % div

def solve():
    modinv = get_modinv(n+1)
    for i in range(1,n+2):
        fact.append(fact[-1]*i%div)
        factinv.append(factinv[-1] * modinv[i] % div)
    return ((partitions(n,k) + (n-1)*partitions(n-1,k))*sum(a)) % div

div = 10**9 + 7
n, k, a = read_data()
fact, factinv = [1], [1]
print(solve())

def read_data():
    n, m = map(int, list(input().strip().split()))
    a = list(map(int, list(input().strip().split())))
    return n, m, a
 
def get_modinv(m):
    modinv = [-1 for _ in range(m+1)]
    modinv[1] = 1
    for i in range(2,m+1):
        modinv[i] = (-(div//i) * modinv[div%i]) % div
    return modinv
 
def partitions(n,k):
    if k >n :
        return 0
    val = 0
    sign = 1
    if k%2 == 1:
        sign = -1
    for i in range(k+1):
        v = (fact[k] * factinv[i] * factinv[k-i] * pow(i,n,div)) % div
        val += v * sign
        val %= div
        sign *= -1
    val *= factinv[k]
    return val % div
 
def solve():
    modinv = get_modinv(n+1)
    for i in range(1,n+2):
        fact.append(fact[-1]*i%div)
        factinv.append(factinv[-1] * modinv[i] % div)
    return ((partitions(n,k) + (n-1)*partitions(n-1,k))*sum(a)) % div
 
div = 10**9 + 7
n, k, a = read_data()
fact, factinv = [1], [1]
print(solve())