1498. Number of Subsequences That Satisfy the Given Sum Condition

class Solution:
    def numSubseq(self, A: List[int], target: int) -> int:
        """  tc O(NlgN) sc O(N) can optimize to O(1) by using math.pow(2,diff,M) 
        main idea: two ptr 
        1. sort 
        2. preprocessing: for each A[i], find max A[j] s.t. A[i] + A[j] <= target ====>
                    for subarray A[i+1] ~ A[j],  can choose to pick or not pick on each element, hence there are 2^(j-i) choices 
                    
                !! here we count 2^(r-l) because we alwayse keep A[i] as min and the subarray after [can include empty subsequence ]
        3. update res for each A[i]
        
        here we can use l,r ptr to move toward each other since array is sorted 
        Note, hidden condition:
        (1) order doesn't matter
        (2) empty is subsequence not count
        (3) no need to deduplicate 
        """
        M = 10**9 + 7 
        A.sort()
        l,r,n = 0, len(A)-1,len(A)
        # cache 2^i  
        exp = [0]*n
        exp[0] = 1
        for i in range(1,n):
            exp[i] = 2*exp[i-1] % M
        res = 0
        while l<= r:
            if A[l] + A[r] > target:
                r -= 1
            else:
                res = (res +exp[r-l])%M #(res + pow(2,r-l,M))%M
                l += 1 
        return res