A hiking club has n members; member i walks at pace[i] metres per minute. A party is any
group of exactly k different members. A party's gap is its fastest pace minus its slowest pace.
Members with equal paces are still different people, so parties are counted by who is in them.
Return the sum of the gaps of all C(n, k) parties, modulo 1_000_000_007. If k > n there are
no parties and the answer is 0.
Examples
Input: pace = [50, 80, 60], k = 2
Output: 60
Explanation: parties {50, 80}, {50, 60}, {80, 60} have gaps 30, 10 and 20.
Input: pace = [70, 40, 70, 90], k = 3
Output: 150
Explanation: {70, 40, 70} -> 30, {70, 40, 90} -> 50, {70, 70, 90} -> 20, {40, 70, 90} -> 50.
Constraints
0 <= n <= 10**5,1 <= k <= 10**50 <= pace[i] <= 10**9- Listing parties is impossible, and a loop over all pairs of members is too slow.
Goals
- Split a sum over subsets into what each element contributes
- Count the subsets in which an element is the largest or the smallest
- Compute many binomial coefficients mod a prime from factorials and inverse factorials