Number of Subsequences That Satisfy the Given Sum Condition

Fix the minimum and maximum

Sort the array. Keep left at a candidate minimum and right at a candidate maximum. If nums[left] + nums[right] <= target, then every subset whose minimum is left and whose remaining members come from positions left+1..right is valid: there are 2^(right-left) choices. Add that count modulo the required modulus and advance left. Otherwise the maximum is too large, so decrement right.

Sorting is O(n log n), the two-pointer sweep is O(n), and precomputing powers is O(n) time and space. The proof relies on sorting: no chosen middle value exceeds the fixed maximum, so it cannot violate the min-plus-max condition. Test one element, values exactly at target, duplicates, no valid subset, and modulo wraparound. Do not enumerate subsets, which is exponential, and do not count combinations without clarifying that the condition is based on each subsequence's minimum and maximum.