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

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.