All problems

Number of Subsequences That Satisfy the Given Sum Condition

Medium · two pointers

A chef has a row of ingredients. The list nums gives the strength of each one. The chef picks a non-empty group of ingredients, and the dish is balanced when the weakest pick plus the strongest pick is at most target.

Count how many non-empty groups are balanced. A group is a choice of positions in nums: two groups are different if they use different positions, even if the strengths are the same. The order of the row does not matter for balance, only which positions are chosen.

A group with a single ingredient counts its strength twice, since it is both the weakest and the strongest.

The count can be very large, so return it modulo 10^9 + 7.

Examples

Example 1

Input: nums = [3, 5, 6, 7], target = 9

Output: 4

The balanced groups are [3], [3, 5], [3, 5, 6] and [3, 6]. For example [3, 7] has 3 + 7 = 10, which is too much.

Example 2

Input: nums = [3, 3, 6, 8], target = 10

Output: 6

The balanced groups are the first 3, the second 3, both 3s, each 3 with the 6, and both 3s with the 6. Any group with the 8 fails, since 3 + 8 = 11.

Example 3

Input: nums = [8, 9], target = 10

Output: 0

Constraints