Count Subsequences Whose Minimum Plus Maximum Stays Within a Target

Given an integer array `nums` and an integer `target`, count the non-empty subsequences of `nums` whose smallest element plus largest element is at most `target`. Because the count can be enormous, return it modulo `10^9 + 7`. A subsequence is chosen by a set of indices, so two subsequences that use different index sets are counted separately even when they contain the same values. Only which elements are chosen matters for the condition, not their order. ### Function Signature ```python def count_subsequences(nums: list[int], target: int) -> int: ``` ### Rules - For a chosen non-empty set of indices, let `lo` be the minimum and `hi` the maximum of the chosen values; for a single element both equal that element. The subsequence qualifies when `lo + hi <= target`. - Count every qualifying non-empty index set exactly once. - Return the count modulo `1_000_000_007`. Return `0` if no subsequence qualifies. ### Constraints - `1 <= len(nums) <= 10^5` - `1 <= nums[i] <= 10^6` - `1 <= target <= 10^6` - The exact count can be as large as `2^100000 - 1`, far beyond any fixed-width integer, which is why it is reported modulo `10^9 + 7`; the returned value is always below `10^9 + 7`. ### Examples **Example 1** - Input: `nums = [2, 3, 5, 8]`, `target = 8` - Output: `6` - Explanation: the qualifying subsequences are `[2]`, `[3]`, `[2, 3]`, `[2, 5]`, `[3, 5]` and `[2, 3, 5]`. A lone `[5]` does not qualify because `5 + 5 = 10`. **Example 2** - Input: `nums = [4, 1, 4]`, `target = 5` - Output: `4` - Explanation: the qualifying index sets are `{1}`, `{0, 1}`, `{1, 2}` and `{0, 1, 2}`, that is `[1]`, `[4, 1]`, `[1, 4]` and `[4, 1, 4]`. The two single-element choices of `4` fail because `4 + 4 = 8`. **Example 3** - Input: `nums = [7, 9]`, `target = 10` - Output: `0` - Explanation: even the smallest element alone gives `7 + 7 = 14`.