Precalculate number of ways to form subsets with n as minimum/maximum for valid n.

Use of (n+1)Cr = nCr * (n+1)/(n+1-r) for efficient calculation of nCr for incrementing n and fixed r

O(n) solution

def solve(balls, k): MOD = 10**9+7 result = 0 n = len(balls) balls.sort()

memo = {}
memo[k-1] = math.comb(k-1, k-1)
for i in range(k, n+1):
    memo[i] = memo[i-1] * i // (i-(k-1))
for i in range(n-k+1):
    result -= balls[i] * memo[n-1-i]
for i in range(k-1, n):
    result += balls[i] * memo[i]
return result % MOD