A sauce bar lines up bottles with heat ratings heat. A flight is any non-empty set of
bottles (chosen by position, so bottles with equal ratings are still different bottles). A flight
is balanced when the mildest rating plus the hottest rating in it lies between lo and hi,
inclusive. A flight of one bottle counts its rating twice.
Return the number of balanced flights modulo 10**9 + 7.
Examples
Input: heat = [3, 1, 4, 2], lo = 4, hi = 5
Output: 8
Explanation: {2}, {1,3}, {1,2,3}, {1,4}, {1,2,4}, {1,3,4}, {1,2,3,4} and {2,3}.
Input: heat = [2, 2, 2], lo = 4, hi = 4
Output: 7
Explanation: every non-empty set of the three bottles has mildest + hottest = 4.
Input: heat = [5, 1, 6, 3, 8], lo = 7, hi = 9
Output: 15
Constraints
0 <= len(heat) <= 10**50 <= heat[i] <= 10**9,0 <= lo <= hi <= 3 * 10**9- Return
0for an empty list. Looping over every (mildest, hottest) pair is O(n^2) and will time out.
Goals
- Count subsets by fixing only their smallest and largest members
- Turn a two-sided range condition into a difference of two one-sided counts