Given an array of integers nums and an integer target.
Return the number of non-empty subsequences of nums such that the sum of the minimum and maximum element on it is less or equal than target.
Since the answer may be too large, return it modulo 10^9 + 7.
 
Example 1:
Input: nums = [3,5,6,7], target = 9
Output: 4
Explanation: There are 4 subsequences that satisfy the condition.
[3] -> Min value + max value <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)

Example 2:
Input: nums = [3,3,6,8], target = 10
Output: 6
Explanation: There are 6 subsequences that satisfy the condition. (nums can have repeated numbers).
[3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]
Example 3:
Input: nums = [2,3,3,4,6,7], target = 12
Output: 61
Explanation: There are 63 non-empty subsequences, two of them don't satisfy the condition ([6,7], [7]).
Number of valid subsequences (63 - 2 = 61).

Example 4:
Input: nums = [5,2,4,1,7,6,8], target = 16
Output: 127
Explanation: All non-empty subset satisfy the condition (2^7 - 1) = 127
 
Constraints:

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^6
1 <= target <= 10^6

Difficulty: interview

Starter code:

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        

Solutions:
class Solution:
    MODS = 10 ** 9 + 7
    def numSubseq(self, nums: List[int], target: int) -> int:
        N = len(nums)
        cal_map = [1]
        for ii in range(1, N):
            cal_map.append(cal_map[-1] * 2 % self.MODS)
        left, right, res = 0, N - 1, 0
        nums.sort()
        while left < N:
            if nums[left] * 2 > target:
                break
            while right - 1 >= left and nums[left] > target - nums[right]:
                right -= 1
            res += cal_map[right - left]
            # print(left, right, cal_map[right - left], nums[left])
            left += 1
        return res % self.MODS
            


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums = sorted(nums)
        mod = int(1e9+7)
        power = [1]*(len(nums)+1)
        for i in range(1,len(nums)):
            power[i] = power[i-1] * 2 % mod;
        
        left,right = 0,len(nums)-1
        res = 0
        while left<=right:
            while left<=right and nums[left]+nums[right]>target:
                right-=1
            
            if left>right:
                break
            res += power[right-left]
            left+=1
            
        return res%mod
        


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums = sorted(nums)
        result = 0
        mod = 10 ** 9 + 7
        l, r = 0, len(nums) - 1
        while l <= r:
            if nums[l] + nums[r] > target:
                r -= 1
            else:
                result = result + pow(2, r-l, mod)
                l += 1
                
        return result % mod

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        ans = 0
        mod = 10 ** 9 + 7
        nums.sort()
        temp = 0
        def bina(i,low,high):
            ans = low - 1 
            while(low<=high):
                mid = (low + high)//2
                if nums[i] + nums[mid] <= target:
                    low = mid + 1
                    ans = mid
                else:
                    high = mid - 1
            return ans - i

        for i in range(len(nums)):
            if nums[i]*2 > target:
                break
            ans = (ans + int(pow( 2,bina(i,i,len(nums)-1) ,mod) ))%mod
            print(ans)
        return ans
        
        
        
                


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        mod = 10**9 + 7
        left = 0
        right = len(nums) - 1
        res = 0 
        while(left <= right):
            if nums[left] + nums[right] > target:
                right -= 1
            else:
                num_inside = right - left
                res = (res + pow(2, num_inside, mod)) % mod
                left += 1
        return res


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        
        n = len(nums)
        l,r,res = 0,n-1,0
        dp = [1]*n
        for i in range(1,n):
            dp[i] = (2*dp[i-1]) % (1000000007)
        while l <= r:
            # 固左动右
            while nums[l]+nums[r] > target and l <= r:
                r-=1
            if l<=r: 
                res += 1                
                res += dp[r-l]-1
                l+=1
            
        return res % (1000000007)
            


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        if not nums:
            return 0
        res = 0
        nums.sort()
        ln = len(nums)
        i = 0
        j = ln-1
        md = pow(10,9)+7
        
        while i <= j:
            if nums[i]+nums[j]<= target:
                res = (res + pow(2, j-i, md))%md
                i += 1
            else:
                j -= 1
        return res
    
            
                    
                    
            
            
        


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        ans = 0
        l = 0
        h = len(nums) - 1
        MOD = 10 ** 9 + 7
        while l <= h:
            if nums[l] + nums[h] <= target:
                ans = (ans + pow(2, h - l, MOD)) % MOD
                l += 1
            else:
                h -= 1
        return ans

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        left= 0
        right = len(nums) - 1
        res = 0
        mod = 10**9 + 7
        while (left <= right):
            if nums[left] + nums[right] <= target:
                res += pow(2, (right - left), mod)
                left += 1
            else:
                right -= 1
        return res % mod



class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        
        
        nums.sort()
        
        i = 0
        
        j = len(nums)-1
        
        result = 0
        
        mod = 10**9+7
        
        while i <= j:
            if nums[i] + nums[j] > target:
                j-=1
            
            else:
                sublen = j-i
                result = (result + pow(2, sublen, mod))% mod
                i +=1
                
        print (result)
        
        return result
        
        


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        '''
         将数组排序，找符合条件的子序列的最小值与最大值
         从每一项开始，寻找符合条件的最大值位置
            In subarray nums[i~j]:
            min = nums[i], max = nums[j]
            nums[i] + nums[j] <= target
            {nums[i], (j - i - 1 + 1 values)}
            Any subset of the right part gives a valid subsequence 
            in the original array. And There are 2^(j - i) ones.
        '''
        n=len(nums)
        nums.sort()
        p=[1]*(n+1)
        for i in range(1,n+1):
            p[i]=p[i-1]<<1
        res=0
        j=n-1
        for i in range(j+1):
            while i<=j and nums[i]+nums[j]>target:
                j-=1
            if i>j:
                continue
            res+=p[j-i]
        return res%(10**9+7)


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        
        if not nums:
            return 0
        nums.sort()
        res = 0
        mod= 10**9+7
        
        l, r = 0, len(nums)-1
        while l <= r:
            
            if nums[l] + nums[r] > target:
                r -= 1
            else:
                res = (res + pow(2, r-l, mod)) % mod
                l += 1
        return res
        # nums.sort()
        # mod = 10**9 + 7
        # left = 0
        # right = len(nums) - 1
        # res = 0 
        # while(left <= right):
        #     if nums[left] + nums[right] > target:
        #         right -= 1
        #     else:
        #         num_inside = right - left
        #         res = (res + pow(2, num_inside, mod)) % mod
        #         left += 1
        # return res

            
            
            
       


class Solution:
    def getCombination( self, start, endPos):
        mod = 10**9 + 7


        #for i in range (1, qty+1):
        #    ncombination = math.factorial(qty)
        #    ncombination = ncombination/(math.factorial(i) * math.factorial(qty-i))
        #    count += ncombination
        #print (count)
        count = pow (2, endPos - start )
        return count % mod
                                         
    def findPos(self,nums,target):
        # 0 1 2,  0,1,2,3
        
        start = 0
        end = len(nums) -1
        while start <= end:

            medium = start + (end - start) // 2
            #print (start, medium, end )
            sumv = nums[0] + nums[medium]
            if sumv > target:
                # go left 
                end = medium -1
            elif sumv == target:
                if (medium == len(nums) -1) or nums[medium +1] != nums[medium]:
                    #found
                    return medium
                else:
                    # look for the rightmost
                    start = medium + 1
            else:
                #sumv < target, check rightone
                if (medium == len(nums) -1) or nums[medium +1] + nums[0] > target:
                    return medium
                else:
                    # go right
                    start = medium + 1
                
        return end 
         
            
        



    def numSubseq2(self, nums: List[int], target: int) -> int:
        mod = 10**9 + 7
        nums.sort()
        #print (nums)
        #for each element, find the max
        #count the number 
        start = 0
        count = 0
        endPos = self.findPos(nums,target)
        print (endPos)
        while (start < len(nums) and start <= endPos and endPos >0):
            if nums[endPos] + nums[start] <= target:
                count += pow (2, endPos - start )
                count = count % mod
                start += 1
            else:               
                endPos -= 1

        return int(count % mod)
    
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        left,right = 0,len(nums)-1
        res = 0
        md = 10**9+7
        while left<=right:
            if nums[left]+nums[right]<=target:
                res=(res+pow(2,right-left,md))%md
                left+=1
            else:right-=1
        return res


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        MOD = 10**9+7
        s = sorted(nums)
        
        powers = [1]
        for _ in s: powers.append(powers[-1] * 2)
        
        j = len(s) - 1
        c = 0
        for i, n in enumerate(s):
            
            while j > i and n + s[j] > target: j -=1
            
            if i <= j and s[i] + s[j] <= target:
                c += powers[j - i]
                # print(i, j, c)
            
        return c % MOD

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums = sorted(nums)
        l, r = 0, len(nums) - 1
        res = 0; mod = 10**9 + 7
        while l <= r:
            if nums[l] + nums[r] <= target:
                res += pow(2, r - l, mod) 
                l += 1
            else:
                r -= 1
        return res % mod
        


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        n = len(nums)
        l,r = 0, n-1
        counts = 0
        res = 0
        
        while True:
            while l<=r and nums[r]+nums[l]>target:
                r -= 1
            if l<=r:
                res += pow(2, (r-l), 10**9+7)
                res %= 10**9 + 7
                l += 1
            else:
                break
            
        return res 


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        # time O(nlogn); space O(1)
        nums.sort()
        left, right = 0, len(nums)-1
        res = 0
        while left <= right:
            if nums[left] + nums[right] <= target:
                res += pow(2, right-left, 10**9+7)
                left += 1
            else:
                right -= 1
        
        return res % (10**9+7)


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        l, r = 0, len(nums) - 1
        res = 0
        mod = 10**9 + 7
        while l <= r:
            if nums[l] + nums[r] > target:
                r -= 1
            else:
                res += pow(2, r - l, mod)
                l += 1
        return res % mod

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        n,result,p1,p2,m=len(nums),0,0,len(nums)-1,1000000007
        nums.sort()
        while(p1<=p2):
            if nums[p1]+nums[p2]<=target:
                result=(result+pow(2,p2-p1,m))%m
                p1+=1
            else:
                p2-=1
        return result

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        start = 0
        end = len(nums) - 1 
        res = 0
        mod = 10**9 + 7 
        
        while start <= end:
            if nums[start] + nums[end] > target:
                end -= 1 
            else:
                res += pow(2,end - start, mod)
                start += 1 
        return res % mod
        


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        l, r = 0, len(nums) - 1
        ans, mod = 0, 10 ** 9 + 7
        while l <= r:
            if nums[l] + nums[r] <= target:
                # If we are using nums[l] as first element (and never be excluded)
                # then there are 2 ** (r - l) options since the other positions can
                # be toggled in or out
                ans += pow(2, r - l, mod)
                l += 1
            else:
                r -= 1
        return ans % mod

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        n = len(nums)
        res = 0
        #one length subsequence
        mod = 10**9 + 7
        i,j = 0,n-1
        
        
        for i in range(n):
            while i<=j and nums[i]+nums[j] > target:
                j-=1
            
            if i<=j and nums[i] + nums[j] <= target:
                res += pow(2,(j-i) , mod)
                res %= mod
        
        return res

'''class Solution:
    def numSubseq(self, A: List[int], target: int) -> int:
        A.sort()
        l, r = 0, len(A) - 1
        res = 0
        mod = 10**9 + 7
        while l <= r:
            if A[l] + A[r] > target:
                r -= 1
            else:
                res += pow(2, r - l, mod)
                l += 1
        return res % mod'''

class Solution:
    def numSubseq(self, A, target):
        A.sort()
        l = 0 
        r = len(A)-1
        res = 0 
        mod = 10**9 + 7
        while l <= r:
            if A[l] + A[r] <= target:
                res += pow(2, r-l,mod)
                l += 1
            else:
                r-=1 
        return res%mod
                


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        left,right = 0,len(nums)-1
        count = 0
        
        dp = [0]*(len(nums)+1)
        for i in range(1,len(nums)+1):
            dp[i]=2*dp[i-1]+1
#        print (\"dp \",dp)
        while left<=right:
           
            while left<=right and nums[left] + nums[right]>target:
                right -=1
            count += dp[right-left+1]
#            print (\"-- \",left,\"  \",right, \"  count =\",count)
            while left<=right and nums[left] + nums[right]<=target:
                left +=1
            count -=dp[right-left+1]  
#            print (\"$$ \",left,\"  \",right, \"  count =\",count)
        
        return count %(10**9 +7)

    
    
    
    def totalS(self,N):
        if N<2: return N
        return 2* self.totalS(N-1) +1


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        
        
        ######Approach 1 log (n^2)
#         nums.sort()
#         if not nums:
#             return 0
        
#         total=0
#         print(nums)
#         for i in range(len(nums)):
#             for j in range(len(nums)-1,i-1,-1):
#                 if nums[i]+nums[j]<=target:
#                     total+=pow(2, j-i, 10**9 + 7)
#                     break
#         return total % (10**9 + 7)

##########Approach 2 log(n) 
        low=0
        high=len(nums)-1
        nums.sort()
        if not nums:
            return 0
        total=0
        while low<=high:
            if nums[low]+nums[high]<=target:
                total+=pow(2, high-low, 10**9 + 7)
                low+=1
            else:
                high-=1
        return total %(10**9 + 7)
                
            


p = 1000000007
    
def modSum(a, b):
    return (a + b) % p

def modProd(a, b):
    return (a * b) % p

def modPow(x, n):
    if n == 0:
        return 1
    
    res = modPow(x, n // 2)
    res = modProd(res, res)
    if n % 2 == 1:
        res = modProd(res, x)
    
    return res;


class Solution:
    def numSubseq(self, arr: List[int], target: int) -> int:
        n = len(arr)
        arr.sort()
        i = 0
        j = n - 1
        res = 0
        while i <= j:
            sum = arr[i] + arr[j]
            if sum > target:
                j -= 1
            else:
                res = modSum(res, modPow(2, j - i))
                i += 1
                
        return res

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        n = len(nums)
        l,r = 0, n-1
        counts = 0
        res = 0
        
        while l<=r:
            if nums[r]+nums[l]>target:
                r -= 1
            else:
                res += pow(2, (r-l), 10**9+7)
                l += 1
            
        return res % (10**9+7)


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        MOD = int(1e9 + 7)
        pw = [1]
        for i in range(1, 100001):
            pw.append(pw[-1]*2%MOD)
        nums.sort()
        i = 0
        j = len(nums)-1
        ret = 0
        for i in range(len(nums)):
            while nums[i] + nums[j] > target:
                j -= 1
                if i > j: return ret
            ret += pw[j-i]
            ret %= MOD
        return ret


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        l, r = 0, len(nums)-1
        res = 0
        mod = 10 **9 + 7
        while l <= r:
            if nums[l] + nums[r] > target:
                r -= 1
            else:
                res += pow(2, r - l, mod)
                l += 1
        return res % mod

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        #3:57pm
        
        
        # first sort it, then use two pointer
        
#         nums.sort()
#         l, r = 0, len(nums)-1
#         res = 0
#         stack = []
        
#         while l <= r and not stack:
#             sums = nums[l] + nums[r]
#             if sums <= target:
#                 stack.append((l, r))
#                 break
#             r -= 1
        
#         while stack:
#             l, r = stack.pop()
#             res += r - l + 1
#             l += 1
#             if l < r and nums[l] + nums[r] <= target:
#                 stack.append((l, r))
#             elif l == r-1 and nums[l] + nums[r] > target:
#                 res += 1
#                 break
                
#         return res

        A = nums
        A.sort()
        l, r = 0, len(A) - 1
        res = 0
        mod = 10**9 + 7
        while l <= r:
            if A[l] + A[r] > target:
                r -= 1
            else:
                res += pow(2, r - l, mod)
                l += 1
        return res % mod

class Solution:
    def getCombination( self, start, endPos):
        mod = 10**9 + 7


        #for i in range (1, qty+1):
        #    ncombination = math.factorial(qty)
        #    ncombination = ncombination/(math.factorial(i) * math.factorial(qty-i))
        #    count += ncombination
        #print (count)
        count = pow (2, endPos - start )
        return count % mod
                                         
    def findPos(self,nums,target):
        # 0 1 2,  0,1,2,3
        
        start = 0
        end = len(nums) -1
        while start <= end:

            medium = start + (end - start) // 2
            #print (start, medium, end )
            sumv = nums[0] + nums[medium]
            if sumv > target:
                # go left 
                end = medium -1
            elif sumv == target:
                if (medium == len(nums) -1) or nums[medium +1] != nums[medium]:
                    #found
                    return medium
                else:
                    # look for the rightmost
                    start = medium + 1
            else:
                #sumv < target, check rightone
                if (medium == len(nums) -1) or nums[medium +1] + nums[0] > target:
                    return medium
                else:
                    # go right
                    start = medium + 1
                
        return end 
         
            
        



    def numSubseq(self, nums: List[int], target: int) -> int:
        mod = 10**9 + 7
        nums.sort()
        #print (nums)
        #for each element, find the max
        #count the number 
        start = 0
        count = 0
        endPos = self.findPos(nums,target)
        print (endPos)
        while (start < len(nums) and start <= endPos and endPos >0):
            if nums[endPos] + nums[start] <= target:
                count += pow (2, endPos - start,mod)
                count = count % mod
                start += 1
            else:               
                endPos -= 1

        return int(count % mod)
    
    def numSubseq2(self, nums: List[int], target: int) -> int:
        nums.sort()
        left,right = 0,len(nums)-1
        res = 0
        md = 10**9+7
        while left<=right:
            if nums[left]+nums[right]<=target:
                res=(res+pow(2,right-left,md))%md
                left+=1
            else:right-=1
        return res


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        # sub sequence 就随便排序了，
        nums.sort()
        cnt = 0
        N = 10 ** 9 + 7
        D = [1] * (len(nums) + 1)
        
        def bisect(x, low, high):
            if high - low <= 1:
                if nums[high] <= x:
                    return high
                else:
                    return low
            
            mid = (low + high) // 2
            if nums[mid] <= x:
                return bisect(x, mid, high)
            else:
                return bisect(x, low, mid)
        
        
        # generate combination number
        for idx in range(1, len(D)):
            D[idx] = D[idx-1] * 2
        
        # print (D)
        
        n = len(nums) - 1
        for idx, i in enumerate(nums):
            if i > target - i:
                break
            else:
                # print(target - i, idx, n)
                best = bisect(target - i, idx, n)
                # print ('best', best, 'idx', idx)
                n = best 
                cnt += D[best - idx]
                
        # print (D)
        return cnt % N
        
        


class Solution:
    def __init__(self):
        mod = 1e9+7
        self.two_power = [0]*100010
        self.two_power[0] = 1
        for i in range(1,len(self.two_power)):
            num = self.two_power[i-1]*2
            if num > mod: num%=mod
            self.two_power[i] = num
            
    
    def numSubseq(self, nums: List[int], target: int) -> int:
        mod = 1e9+7
        nums = sorted(nums)
        sind = 0
        eind = len(nums)-1
        ans = 0
        
        # print(self.two_power[:20])
        
        while sind <= eind:
            if nums[sind]+nums[eind] > target:
                eind-=1
            else:
                ans+=self.two_power[eind-sind]
                if ans > mod: ans%=mod
                sind+=1
        return int(ans)

class Solution:
    #Version 1: Sliding window
    #Count the mismatch count
    #TC: O(nlogn), SC: O(1)
    '''
    def numSubseq(self, nums: List[int], target: int) -> int:
        M = 10**9 + 7
        mismatch = 0
        nums.sort()
        base = 0
        for k in range(len(nums)):
            if nums[k]*2 > target:
                while base > 0 and nums[base] + nums[k] > target:
                    base -= 1
                while base < k and nums[base] + nums[k] <= target:
                    base += 1
                mismatch += pow(2, k-base, M)
        return (pow(2, len(nums), M) - 1 - mismatch) % M
    '''
    
    #Version 2: Two sum
    #Once the window is valid, we can add the number of subsequences with left or right number
    #TC: O(nlogn), SC: O(1)
    '''
    def numSubseq(self, nums: List[int], target: int) -> int:
        M = 10**9 + 7
        pows = [1]*(len(nums)+1)
        for k in range(1, len(pows)):
            pows[k] = (pows[k-1]<<1) % M
        ans = 0
        nums.sort()
        left = 0
        right = len(nums) - 1
        while left <= right:
            total = nums[left] + nums[right]
            if total > target:
                right -= 1
            else:
                ans = (ans + pows[right-left]) % M
                left += 1
        return ans
    '''
    
    #Version 3: Sliding window
    #Consider the valid count
    #TC: O(n^2), SC: O(1)
    def numSubseq(self, nums: List[int], target: int) -> int:
        from bisect import bisect_left
        M = 10**9 + 7
        pows = [1]*(len(nums)+1)
        for k in range(1, len(pows)):
            pows[k] = (pows[k-1]<<1) % M
        ans = 0
        nums.sort()
        base = 0
        for k in range(len(nums)):
            if nums[k]*2 <= target:
                ans += pow(2, k, M)
            else:
                base = bisect_left(nums, target - nums[k] + 1)
                ans += (pow(2, base, M) - 1) * pow(2, k-base, M)
            #print(k, base, ans)
        return ans % M



class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        a = nums
        a.sort()
        t = target
        while a and a[-1] > t:
            a.pop()
       # ans = sum([2 * x <= t for x in a])
        ans = 0
        l, h = 0, len(a) - 1
        M = 10 ** 9 + 7
        while l <= h:
            while l <= h and a[h] + a[l] > t:
                h -= 1
            if l <= h and a[h] + a[l] <= t:
                ans += ((1 << (h - l)))
                ans %= M
            l += 1
        return ans


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        le = len(nums)
        res = 0
        mod=10**9+7
        for i in range(le):
            if nums[i]*2<=target:
                lo,hi = i,le-1
                while hi>lo:
                    mid = (hi+lo+1)//2
                    if nums[i]+nums[mid]<=target:
                        lo = mid
                    else:
                        hi = mid-1
                res += pow(2,lo-i,mod)
                res%=mod
            else:
                break
        return res

class Solution:
    def numSubseq(self, A: List[int], target: int) -> int:
        A.sort()
        l, r = 0, len(A) - 1
        res = 0
        mod = 10**9 + 7
        while l <= r:
            if A[l] + A[r] > target:
                r -= 1
            else:
                res += pow(2, r - l, mod) #For each elements in the subarray A[i+1] ~ A[j],we can pick or not pick
                l += 1
        return res % mod

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        mod = 10**9 + 7
        sum, l, r = 0, 0, len(nums)-1
        while l <= r:
            if nums[l] + nums[r] > target:
                r -= 1
            else:
                sum += (1 << r-l) % mod
                l += 1
        return sum % mod

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        subsequences = 0
        nums.sort()
        l, r = 0, len(nums) - 1
        while l <= r:
            if nums[l] + nums[r] <= target:
                subsequences += 1<<(r-l)
                l += 1
            else:
                subsequences += 1 if 2*nums[r] <= target else 0
                r -= 1
            subsequences %= 1000000007
        return subsequences

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        left_idx = 0
        right_idx = len(nums) - 1
        res = 0
        mod = 10**9 + 7
        while left_idx <= right_idx:
            if nums[left_idx] + nums[right_idx] > target:
                right_idx -= 1
            else:
                res += 1 << (right_idx - left_idx)
                res %= mod
                left_idx += 1
        return res

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        
        if nums[0] * 2 > target:
            return 0
        
        MOD = 10 ** 9 + 7
        count = 0
        left, right = 0, len(nums) - 1
        while left <= right:
            if nums[left] + nums[right] > target:
                right -= 1
            else:
                count = (count + (1 << (right - left))) % MOD
                left += 1
        return count

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums = sorted(nums)
        l, r = 0,len(nums)-1
        MOD = 10**9+7 
        res = 0
        while l<=r:
            if nums[l]+nums[r] > target:
                r -= 1
            else:
                res = (res + (1<<(r-l))) % MOD
                # print(res)
                l += 1
        return res

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        
        if nums[0] * 2 > target:
            return 0
        
        MOD = 10 ** 9 + 7
        count = 0
        left, right = 0, len(nums) - 1
        while left <= right:
            if nums[left] + nums[right] > target:
                right -= 1
            else:
                # need to use fast_pow here
                count = (count + (1 << (right - left))) % MOD
                left += 1
        return count

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        
     
        nums.sort()
        n = len(nums)
        left = 0
        right = n - 1
        res = 0
        mod = 10 **9 + 7
        
        while left <=right:
            while left <= right and nums[right] + nums[left] > target:
                right-= 1
            if right < left:
                return res
            res = (res + (1 <<  (right - left))) % mod
            left+= 1
        
        
        return res;
       


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        MOD = 10 ** 9 + 7
        nums.sort()
        ans = 0
        r = len(nums) - 1
        for l in range(len(nums)):
            while l <= r and nums[l] + nums[r] > target:
                r -= 1
            if l <= r:
                ans += 1 << (r - l)
                ans %= MOD
        return ans

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        
        if nums[0] * 2 > target:
            return 0
        
        MOD = 10 ** 9 + 7
        count = 0
        left, right = 0, len(nums) - 1
        while left <= right:
            while left <= right and nums[left] + nums[right] > target:
                right -= 1
            if right < left:
                break
            count = (count + (1 << (right - left))) % MOD
            left += 1
        return count

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        
        nums.sort()
        
        ans = 0
        
        for i in range(len(nums)):
            
            if 2 * nums[i] <= target:
                ans += 1
                
            lo, hi = i + 1, len(nums) - 1
            
            while lo < hi:
                m = (lo + hi) // 2 + 1
                
                if nums[i] + nums[m] > target:
                    hi = m - 1
                else:
                    lo = m

            if nums[i] + nums[hi] <= target:
                ans += (1 << (hi - i)) - 1
                
        return ans % (10 ** 9 + 7)

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        mod = 10**9 + 7
        left = 0
        right = len(nums) - 1
        res = 0 
        while(left <= right):
            if nums[left] + nums[right] > target:
                right -= 1
            else:
                num_inside = right - left
                res = (res + pow(2, num_inside, mod)) % mod
                left += 1
        return res

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        a = nums
        a.sort()
        t = target
        while a and a[-1] > t:
            a.pop()
        ans = sum([2 * x <= t for x in a])
        l, h = 0, len(a) - 1
        M = 10 ** 9 + 7
        while l + 1 <= h:
            while l + 1 <= h and a[h] + a[l] > t:
                h -= 1
            if l + 1 <= h and a[h] + a[l] <= t:
                ans += ((1 << (h - l)) - 1)
                ans %= M
            l += 1
        return ans


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        le = len(nums)
        res = 0
        mod=10**9+7
        for i in range(le):
            if nums[i]*2<=target:
                lo,hi = i,le-1
                while hi>lo:
                    mid = (hi+lo+1)//2
                    if nums[i]+nums[mid]<=target:
                        lo = mid
                    else:
                        hi = mid-1
                res += pow(2,lo-i,mod)
        return res %mod

class Solution:
    #Version 1: Sliding window
    #Count the mismatch count
    #TC: O(nlogn), SC: O(1)
    '''
    def numSubseq(self, nums: List[int], target: int) -> int:
        M = 10**9 + 7
        mismatch = 0
        nums.sort()
        base = 0
        for k in range(len(nums)):
            if nums[k]*2 > target:
                while base > 0 and nums[base] + nums[k] > target:
                    base -= 1
                while base < k and nums[base] + nums[k] <= target:
                    base += 1
                mismatch += pow(2, k-base, M)
        return (pow(2, len(nums), M) - 1 - mismatch) % M
    '''
    
    #Version 2: Two sum
    #Once the window is valid, we can add the number of subsequences with left or right number
    #TC: O(nlogn), SC: O(1)
    '''
    def numSubseq(self, nums: List[int], target: int) -> int:
        M = 10**9 + 7
        pows = [1]*(len(nums)+1)
        for k in range(1, len(pows)):
            pows[k] = (pows[k-1]<<1) % M
        ans = 0
        nums.sort()
        left = 0
        right = len(nums) - 1
        while left <= right:
            total = nums[left] + nums[right]
            if total > target:
                right -= 1
            else:
                ans = (ans + pows[right-left]) % M
                left += 1
        return ans
    '''
    
    def numSubseq(self, nums: List[int], target: int) -> int:
        M = 10**9 + 7
        pows = [1]*(len(nums)+1)
        for k in range(1, len(pows)):
            pows[k] = (pows[k-1]<<1) % M
        ans = 0
        nums.sort()
        base = 0
        for k in range(len(nums)):
            if nums[k]*2 <= target:
                ans += pow(2, k, M)
            else:
                while base > 0 and nums[base] + nums[k] > target:
                    base -= 1
                while base < k and nums[base] + nums[k] <= target:
                    base += 1
                ans += (pow(2, base, M) - 1) * pow(2, k-base, M)
            #print(k, base, ans)
        return ans % M



class Solution:
    #Version 1: Sliding window
    #Count the mismatch count
    #TC: O(nlogn), SC: O(1)
    '''
    def numSubseq(self, nums: List[int], target: int) -> int:
        M = 10**9 + 7
        mismatch = 0
        nums.sort()
        base = 0
        for k in range(len(nums)):
            if nums[k]*2 > target:
                while base > 0 and nums[base] + nums[k] > target:
                    base -= 1
                while base < k and nums[base] + nums[k] <= target:
                    base += 1
                mismatch += pow(2, k-base, M)
        return (pow(2, len(nums), M) - 1 - mismatch) % M
    '''
    
    #Version 2: Two sum
    #Once the window is valid, we can add the number of subsequences with left or right number
    #TC: O(nlogn), SC: O(1)
    '''
    def numSubseq(self, nums: List[int], target: int) -> int:
        M = 10**9 + 7
        pows = [1]*(len(nums)+1)
        for k in range(1, len(pows)):
            pows[k] = (pows[k-1]<<1) % M
        ans = 0
        nums.sort()
        left = 0
        right = len(nums) - 1
        while left <= right:
            total = nums[left] + nums[right]
            if total > target:
                right -= 1
            else:
                ans = (ans + pows[right-left]) % M
                left += 1
        return ans
    '''
    
    #Version 3: Sliding window
    #Consider the valid count
    #TC: O(n^2), SC: O(1)
    def numSubseq(self, nums: List[int], target: int) -> int:
        from bisect import bisect_left
        M = 10**9 + 7
        pows = [1]*(len(nums)+1)
        for k in range(1, len(pows)):
            pows[k] = (pows[k-1]<<1) % M
        ans = 0
        nums.sort()
        base = 0
        for k in range(len(nums)):
            if nums[k]*2 <= target:
                ans += pow(2, k, M)
            else:
                # while base > 0 and nums[base] + nums[k] > target:
                #     base -= 1
                # while base < k and nums[base] + nums[k] <= target:
                #     base += 1
                base = bisect_left(nums, target - nums[k]+1)
                ans += (pow(2, base, M) - 1) * pow(2, k-base, M)
            #print(k, base, ans)
        return ans % M



class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        ans = 0
        mod = 10 ** 9 + 7
        nums.sort()
        temp = 0
        def bina(i,low,high):
            ans = low - 1 
            while(low<=high):
                mid = (low + high)//2
                if nums[i] + nums[mid] <= target:
                    low = mid + 1
                    ans = mid
                else:
                    high = mid - 1
            return ans - i

        for i in range(len(nums)):
            if nums[i]*2 > target:
                break
            ans = (ans + int(pow( 2,bina(i,i,len(nums)-1) ,mod) ))%mod
        return ans
        
        
        
                


# binary search, O(nlogn)
class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        MOD = 10 ** 9 + 7
        nums.sort()
        
        def bsearch(t, l, r):
            if l > r: return -1
            while l < r:
                m = (l + r + 1) // 2
                if nums[m] <= t:
                    l = m
                else:
                    r = m - 1
            return l if nums[l] <= t else -1
        
        res = 0
        for i, n in enumerate(nums):
            ind = bsearch(target - n, 0, i - 1)
            must_have = pow(2, ind + 1, MOD) - 1
            may_have = pow(2, max(0, i - ind - 1), MOD)
            res = (res + must_have * may_have) % MOD
            
        # add special case of single element subsequence
        res = (res + sum(2 * n <= target for n in nums)) % MOD
        return res
        # AC: 2320 ms, beats 41.74%, 25.2 MB, beats 81.62%
            


# binary search, O(nlogn)
class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        MOD = 10 ** 9 + 7
        nums.sort()
        
        def bsearch(t, l, r):
            if l > r: return -1
            while l < r:
                m = (l + r + 1) // 2
                if nums[m] <= t:
                    l = m
                else:
                    r = m - 1
            return l if nums[l] <= t else -1
        
        res = 0
        for i, n in enumerate(nums):
            ind = bsearch(target - n, 0, i - 1)
            must_have = pow(2, ind + 1, MOD) - 1
            may_have = pow(2, max(0, i - ind - 1), MOD)
            res = (res + must_have * may_have) % MOD
            
        # add special case of single element subsequence
        res = (res + sum(2 * n <= target for n in nums)) % MOD
        return res
        # AC: ms, beats, MB, beats
            


MD = 10 ** 9 + 7

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        if nums is None or not nums:
            return 0
        
        N = len(nums)
        
        nums.sort()
        
        start = 0
        end = N - 1
        
        ret = len([d for d in nums if d + d <= target])
        
        while start < end:
            while start < end and nums[start] + nums[end] > target:
                end -= 1
                
            if start < end:
                ret = (ret + self.fast_pow(2, MD, end - start) - 1) % MD
                start += 1
                
        return ret
    
    def fast_pow(self, a, md, n):
        if n == 0:
            return 1 % md
        
        if n == 1:
            return a % md
        
        ret = self.fast_pow(a, md, n // 2)
        ret = (ret * ret ) % md
        
        if n % 2 == 1:
            ret = (ret * a) % md
        
        return ret


class Solution:

    def numSubseq(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1
        ans = 0
        m = 10 ** 9 + 7
        nums.sort()
        while l <= r:
            if (nums[l] + nums[r] > target):
                r -= 1
            else:
                ans += pow(2, r - l, m)
                l += 1
        return ans % m

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        ## two pointer solution
        nums.sort()
        ans = 0
        for i in range(len(nums)):
            if 2*nums[i]>target:
                break
            hi = len(nums)-1
            lo = i
            while lo<=hi:
                mid = (hi+lo)//2
                if nums[i]+nums[mid] > target:
                    hi = mid - 1
                else:
                    lo = mid + 1
            ans = ( ans+ (( 1<<(hi-i)) ) )% (10**9+7) 
        return ans            
        
        


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums = sorted(nums)
        mod = 10**9 + 7
        i, n = 0, len(nums)
        pows = [0] * n
        p = 1
        while i < n:
            pows[i] = p
            p = 2 * p
            i += 1
        
        # print(pows)
        # print(nums)
        l, r = 0, n-1
        res = 0
        while l <= r:
            # print(l, r)
            if nums[l] + nums[r] <= target:
                res = (res + pows[r-l]) % mod
                l += 1
            else:
                r -= 1
                
        return int(res)


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        j = len(nums)-1
        ans = 0
        for i, n in enumerate(nums):
            while j >= i and n + nums[j] > target:
                j -= 1
            if j >= i:
                ans += 1 << (j-i)
                ans %= 1000000007
        return ans

class Solution:
    def get_val(self,arr,i,m1,m2,target):
        if(i==len(arr)):
            return 0
        x = m1
        y = m2
        ct = 0
        if(m1+m2<target):
            ct += 1
        for j in range(i+1,len(arr)):
            m1 = min(x,arr[j])
            m2 = max(y,arr[j])
            if(m1+m2>target):
                continue
            ct += self.get_val(arr,j,m1,m2,target)
        return ct
    
    def get_smallest_idx(self,arr,i,j,x):
        if(arr[i]>x):
            return -1
        l = i
        h = j
        while(l<=h):
            mid = int((l+h)/2)
            if(arr[mid]>x):
                h = mid -1
            else:
                if(mid==h or arr[mid+1]>x):
                    return mid
                else:
                    l = mid + 1
        
    def numSubseq(self, nums: List[int], target: int) -> int:
        
        '''ct = 0
        for i in range(len(nums)):
            m1 = nums[i]
            m2 = nums[i]
            ct += self.get_val(nums,i,m1,m2,target)
        return ct%(10**9+7)'''
        
        nums.sort()
        ct = 0
        N = len(nums)
        j = N-1
        s = [1 for i in range(N)]
        for i in range(1,N):
            s[i] = 2*s[i-1]
        for i in range(N):
            while(j>=i and nums[i]+nums[j]>target):
                j -= 1
            if(j<i):
                return ct%(10**9+7)
            ct += s[j-i]
        return ct%(10**9+7)
        
    


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        l,r=0,len(nums)-1
        ans=0
        while(l<=r):
            # print(l,r,ans)
            if(nums[l]+nums[r]<=target):
                ans=(ans+(1<<(r-l)))%(10**9+7)
                l+=1
            else:
                r-=1
        return ans

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        
        N = 10**9+7
        
        counts = Counter([num for num in nums if num < target])        
        nums = sorted(list(counts.keys()))
        total = sum(counts.values())
        ans = 0
        left, right = 0, len(nums)-1
        while left <= right:
            if nums[left] + nums[right] <= target:
                a = counts[nums[left]]
                total -= a
                ans = (ans + ((1<<a)-1)*(1<<total)) % N
                left += 1
            else:
                total -= counts[nums[right]]
                right -= 1

        return ans
                
        
        
        


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        result = 0
        right_boundary = len(nums) - 1
        for index, num in enumerate(nums):
            if num * 2 > target:
                break
            left = index
            right = right_boundary
            while left < right:
                mid = (left + right + 1) // 2
                if nums[mid] + num <= target:
                    left = mid
                else:
                    right = mid - 1
            right_boundary = left
            tail_length = right_boundary - index
            result += 1 << tail_length
            result %= 10 ** 9 + 7
        
        return result


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        ## two pointer solution
        nums.sort()
        ans = 0
        for i in range(len(nums)):
            if 2*nums[i]>target:
                break
            hi = len(nums)-1
            lo = i
            while lo<=hi:
                mid = (hi+lo)//2
                if nums[i]+nums[mid] > target:
                    hi = mid - 1
                else:
                    lo = mid + 1
            print(hi)
            ans = ( ans+ (( 1<<(hi-i)) ) )% (10**9+7) 
        return ans            
        
        


class Solution:
  def numSubseq(self, nums: List[int], target: int) -> int:
    # One very important lesson to learn from this problem: if asking for subsequences, see if
    # the problem requires some kind of ordering. If not, then you can safely sort the array!
    # Any subset of A is a subsequence (if you put it back into the original order).
    # This problem then becomes trivial. Sort nums, then for each A[i] find the maximum A[j]
    # s.t. A[i] + A[j] <= target. Once you've found A[j], notice that every element in [i + 1, j]
    # can be turned on or off, so that's 2^(j - i) subsequences (notice we cannot turn off A[i] because
    # we are counting \"all subsequences whose min element is A[i]\"). How do we prove this counts
    # every valid subsequence? Because every valid subsequence has a min element, and we consider
    # every A[i] as the min element. So as long as our logic for finding \"number of subsequences whose
    # min element is A[i]\" is correct, we should count all valid subsequences. 
    nums.sort()
    ret, l, r = 0, 0, len(nums) - 1
    
    p, pw = [], 1
    for d in range(len(nums)):
      p.append(pw)
      pw <<= 1
      
    while l <= r:
      if nums[l] + nums[r] <= target:
        ret = (ret + p[r - l]) % (10**9 + 7)  # count all subsequences whose min element is nums[l]
        l += 1                                    # we never have to consider nums[l] as the min element again
      else:
        r -= 1
    return ret


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        ans, left, right = 0, 0, len(nums)-1        
        # Get rid of numbers that can never be included in the subsequences
        while right >= 0 and nums[right] + nums[left] > target:
            right -= 1
        
        while right >= 0:
            complement = target - nums[right]
            if nums[right] <= complement:
                if right >= left:
                    ans += (1 << (right + 1)) - 1
                else:
                    ans += (1 << (left)) - 1
                break
            else:
                while nums[left] <= complement:
                    left += 1
                
                if left == right:
                    ans += (1 << (left + 1)) - 2 # full empty & nums[right] itself
                    break
                else:
                    ans += ((1 << left) - 1) * (1 << (right - left))            
            right -= 1
            # ans = ans % (10 ** 9 + 7)
            
        return ans % (10 ** 9 + 7)
    
    
# [5,5]
# 10

# [4,6]
# 10


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        ans, left, right = 0, 0, len(nums)-1        
        # Get rid of numbers that can never be included in the subsequences
        while right >= 0 and nums[right] + nums[left] > target:
            right -= 1
        
        while right >= left:
            complement = target - nums[right]
            if nums[right] <= complement:
                ans += (1 << (right + 1)) - 1
                break
            else:
                while nums[left] <= complement:
                    left += 1
                
                if left == right:
                    ans += (1 << (right + 1)) - 2 # full empty & nums[right] itself
                else:
                    ans += ((1 << left) - 1) * (1 << (right - left))            
            right -= 1
            
        return ans % (10 ** 9 + 7)
    
    
# [5,5]
# 10

# [4,6]
# 10


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        ans, left, right = 0, 0, len(nums)-1        
        # Get rid of numbers that can never be included in the subsequences
        while right >= 0 and nums[right] + nums[left] > target:
            right -= 1
        
        while right >= 0:
            complement = target - nums[right]
            if nums[right] <= complement:
                ans += (1 << (right + 1)) - 1
                break
            else:
                while nums[left] <= complement:
                    left += 1
                
                if left == right:
                    ans += (1 << (right + 1)) - 2 # full empty & nums[right] itself
                    break
                else:
                    ans += ((1 << left) - 1) * (1 << (right - left))            
            right -= 1
            
        return ans % (10 ** 9 + 7)
    
    
# [5,5]
# 10

# [4,6]
# 10


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        ans, left, right = 0, 0, len(nums)-1        
        while right >= left:
            complement = target - nums[right]
            if nums[right] <= complement:
                ans += (1 << (right + 1)) - 1
                break
            else:
                while nums[left] <= complement:
                    left += 1
                
                if left == right:
                    ans += (1 << (right + 1)) - 2 # full empty & nums[right] itself
                else:
                    ans += ((1 << left) - 1) * (1 << (right - left))            
            right -= 1
            
        return ans % (10 ** 9 + 7)

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        dic = dict()
        for x in nums:
            if x not in dic:
                dic[x] = 0
            dic[x] += 1
        hulu = sorted(list(dic.keys()))
        dahulu = [0]
        for x in hulu:
            dahulu.append(dahulu[-1]+dic[x])
        dahulu = dahulu[1:]
        # print(dahulu)
        
        output = 0
        
        start = 0
        end = len(hulu)-1
        while start<len(hulu):
            while end>=start:
                if hulu[start]+hulu[end]<=target:
                    # print([1,start,end,output])
                    output += (2**dic[hulu[start]]-1)*(2**(dahulu[end]-dahulu[start]))
                    break
                else:
                    end -= 1
            # print([start,end,output])
            start += 1
            
            
        return output%(10**9+7)
                    
                
        


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        ans = 0
        M = 10 ** 9 + 7
        l, r = 0, len(nums) - 1
        while l <= r:
            if nums[l] + nums[r] > target:
                r -= 1
            else:
                ans += 2 ** (r - l)
                l += 1
        return ans % M

class Solution:
    def numSubseq(self, arr: List[int], target: int) -> int:
        
        arr=sorted(arr)
        l=0
        r=len(arr)-1
        
        mod=1000000007
        ans=0
        while(l<=r):
            if(arr[l]+arr[r] > target):
                r-=1    
            else:
                ans+=pow(2,r-l)
                l+=1
                
        return ans%mod
                

        
        
        


class Solution:
    MOD = 10**9 + 7

    def numSubseq(self, nums: List[int], target: int) -> int:
        n = len(nums)
        nums.sort()
        
        count = 0
        i, j = 0, n - 1
        while i <= j:
            if nums[i] + nums[j] > target:
                j -= 1
                
                continue

            len_ = j - i + 1
            count += 2**(len_ - 1)
                
            i += 1
                    
        return count % self.__class__.MOD


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums = sorted(nums)
        n = len(nums)
        count = 0
        i, j = 0, n-1
        while i <= j:
            tot = nums[i] + nums[j]
            if tot <= target:
                count += int(2**(j-i)) 
                i += 1
            else:
                j -= 1
         
        return count % int(1e9 + 7)

class Solution:
    MOD = 10**9 + 7

    def numSubseq(self, nums: List[int], target: int) -> int:
        n = len(nums)
        nums.sort()
        
        count = 0
        i, j = 0, n - 1
        while i <= j:
            if nums[i] + nums[j] > target:
                j -= 1
                
                continue

            len_ = j - i + 1
            if len_ == 1:
                count += 1
            else:
                count += 2**(len_ - 1)
                
            i += 1
                    
        return count % self.__class__.MOD


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        res = 0
        end = len(nums)-1
        nums.sort()
        for i in range(len(nums)):
            while nums[i] + nums[end] > target:
                if end > i:
                    end = end-1
                else:
                    return res % (10**(9)+7)
            res += pow(2, end - i)
        return res % (10**(9)+7)

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        ans, left, right = 0, 0, len(nums)-1        
        # Get rid of numbers that can never be included in the subsequences
        while right >= 0 and nums[right] + nums[left] > target:
            right -= 1
        
        while right >= 0:
            complement = target - nums[right]
            if nums[right] <= complement:
                if right >= left:
                    ans += (1 << (right + 1)) - 1
                else:
                    ans += (1 << (left)) - 1
                break
            else:
                while nums[left] <= complement:
                    left += 1
                
                if left == right:
                    ans += (1 << (left + 1)) - 2 # full empty & nums[right] itself
                    break
                else:
                    ans += ((1 << left) - 1) * (1 << (right - left))            
            right -= 1
            ans = ans % (10 ** 9 + 7)
            
        return ans % (10 ** 9 + 7)
    
    
# [5,5]
# 10

# [4,6]
# 10


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        l, r, count = 0, len(nums)-1, 0
        mod = 10**9 + 7
        while l <= r:
            sums = nums[l] + nums[r]
            if sums > target:
                r -= 1
            else:
                count += 2**(r-l)
                l += 1
        return count % mod


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        # time O(nlogn); space O(1)
        nums.sort()
        left, right = 0, len(nums) - 1
        res = 0
        while left <= right:
            if nums[left] + nums[right] <= target:
                res += pow(2, right-left)
                left += 1
            else:
                right -= 1
        
        return res % (10**9+7)


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        if nums[0]*2>target:
            return 0
        
        res=0
        l,r=0,len(nums)-1
        while l<=r:
            if nums[l]+nums[r]<=target:
                res+=2**(r-l)
                l+=1
            else:
                r-=1
        return res%(10**9+7)

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        l, r = 0, len(nums) - 1
        res = 0
        while l <= r:
            if nums[l] + nums[r] > target:
                r -= 1
            else:
                res += 2 ** (r - l)
                l += 1
        return res % (10**9+7)

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        res = 0
        nums.sort()
        start, end = 0, len(nums) - 1
        while start < end:
            if nums[start] + nums[end] <= target:
                res += pow(2, end - start)
                start += 1
            else:
                end -= 1
        
        if nums[start] * 2 <= target:
            res += 1

        _, res = divmod(res, pow(10, 9) + 7)
        return res
            


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        res = 0
        i = 0
        j = len(nums) - 1
        while i < len(nums):
            
            if target - nums[i] < nums[i]: 
                i = i + 1
                continue
            while j > i:
                if nums[j] + nums[i] <= target: break
                j = j - 1
            res = 2**(j - i) + res
            i = i + 1
        return res % (10**9+7)
    


from typing import List

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int: 
        res = 0
        end = len(nums)-1
        nums.sort()
        for start in range(len(nums)):
            while nums[start] + nums[end] > target:
                if end > start:
                    end -= 1
                else:
                    return res % (10**9 + 7)
            res += 2 ** (end - start)
        return res % (10**9 + 7)

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        l, r = 0, len(nums) - 1
        ans, mod = 0, 10 ** 9 + 7
        while l <= r:
            if nums[l] + nums[r] <= target:
                ans += 2 ** (r - l)
                l += 1
            else:
                r -= 1
        return ans % mod

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        
        nums.sort()
        
        l,r = 0,len(nums)-1
        
        res = 0
        
        while l <= r:
            
            if nums[l] + nums[r] > target:
                
                r -= 1
                
            else:
                
                res += pow(2,r-l)
                
                l += 1
        
        return res % ((10**9) + 7)
                
                


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        print(nums)

        left = 0
        right = len(nums) - 1

        res = 0

        while(left < right):

            min_v = nums[left]
            max_v = nums[right]

            sum = min_v + max_v

            if sum <= target:
                count = right - left 
                res = res + 2**count
                left += 1
            else:
                right -= 1

        if nums[left]*2 <= target:
            res += 1

        return res % (10**9 + 7)
            


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        left, right = 0, len(nums) - 1
        power_set = 0
        
        while left <= right:
            if nums[left] + nums[right] <= target:
                power_set += 2 ** (right - left)
                left += 1
            
            elif nums[left] + nums[right] > target:
                right -= 1
        
        return power_set % (10 ** 9 + 7) 


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        l = 0
        r = len(nums) - 1
        res = 0
        while True :
            while r >= l and (nums[l] + nums[r]) > target :
                r = r - 1
            #print(l, r)
            if l <= r :
                res = res + (2 ** (r - l))
            else :
                break
            l = l + 1
        return res % (10 ** 9 + 7)

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        mod = 10**9 + 7
        nums.sort()
        n = len(nums)
        left = 0
        right = n - 1
        count = 0
        while left <= right:
            t = nums[left] + nums[right]
            if t > target:
                right -= 1
            else:
                count += 2**(right - left)
                left += 1
            
        return count % mod


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        MOD = 10 ** 9 + 7
        nums.sort()

        res = 0
        l = 0
        n = len(nums)
        pow2 = [1]
        for x in range(1, n + 1):
            pow2.append(pow2[-1] * 2 % MOD)
        
        j = n - 1
        for i in range(n):
            while j and nums[i] + nums[j] > target:
                j -= 1
            if i <= j and nums[i] + nums[j] <= target:
                res += pow2[j - i]
                res %= MOD
        return res
        
        # self made, two pointer, TLE, too many redundant calculations
        MODULO = 10 ** 9 + 7
        nums.sort()
        
        res = 0
        l = 0
        n = len(nums)
        
        while l < n and nums[l] * 2 <= target:
            r = l
            while r < n and nums[l] + nums[r] <= target:
                r += 1
            if l <= r < n:
                if l == r and nums[l] + nums[r] <= target:
                    res += 1
                elif l < r and nums[l] + nums[r - 1] <= target:
                    res += (2 ** (r - l - 1)) % MODULO
            elif r == n and nums[l] + nums[r - 1] <= target:
                r -= 1
                res += (2 ** (r - l)) % MODULO
            l += 1
        return res % MODULO
        
        # self made, DFE, TLE
#         self.res = 0
#         end_idx = bisect.bisect_left(nums, target)
#         self.dfs(nums, 0, end_idx, [], target)

#         return self.res % MODULO

#     def dfs(self, nums, start, end_idx, cur, target):
#         if cur and cur[0] + cur[-1] > target:
#             return

#         if cur and cur[0] + cur[-1] <= target:
#             self.res += 1

#         for i in range(start, end_idx):
#             if nums[start] > target:
#                 return
#             cur.append(nums[i])
#             self.dfs(nums, i + 1, end_idx, cur, target)
#             cur.pop()


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        md=10**9 + 7
        left=0
        res=0
        right=len(nums)-1
        while(left<=right):
            if nums[left]+nums[right]<=target:
                res=(res+pow(2,right-left,md))%md
                left=left+1
            else:
                right=right-1
        return res

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        i,j, count = 0, len(nums) - 1, 0
        
        while i <= j:    
            if nums[i] + nums[j] <= target:
                count += int(pow(2, j - i - 1) * 2)
                i += 1
            else:
                j -= 1
                
        
        return count % (pow(10, 9) + 7)

import math
class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        i,j, count = 0, len(nums) - 1, 0
        
        while i <= j:    
            if nums[i] + nums[j] <= target:
                count += math.floor(pow(2, j - i -1) * 2)
                i += 1
            else:
                j -= 1
                
        
        return count % (pow(10, 9) + 7)

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        if not nums:
            return 0
        
        nums.sort()
        
        MOD = 10 ** 9 + 7
        
        res = 0
        j = len(nums) - 1
        
        for i in range(len(nums)):
            while i <= j and nums[i] + nums[j] > target:
                j -= 1
                
            if i <= j and nums[i] + nums[j] <= target:
                res = (res + 2 ** (j - i))
                if res >= MOD:
                    res -= MOD
            
        return res % MOD

class Solution:
    #Version 1: Sliding window
    #Count the mismatch count
    #TC: O(nlogn), SC: O(1)
    '''
    def numSubseq(self, nums: List[int], target: int) -> int:
        M = 10**9 + 7
        mismatch = 0
        nums.sort()
        base = 0
        for k in range(len(nums)):
            if nums[k]*2 > target:
                while base > 0 and nums[base] + nums[k] > target:
                    base -= 1
                while base < k and nums[base] + nums[k] <= target:
                    base += 1
                mismatch += pow(2, k-base, M)
        return (pow(2, len(nums), M) - 1 - mismatch) % M
    '''
    
    #Version 2: Two sum
    #Once the window is valid, we can add the number of subsequences with left or right number
    #TC: O(nlogn), SC: O(1)
    '''
    def numSubseq(self, nums: List[int], target: int) -> int:
        M = 10**9 + 7
        pows = [1]*(len(nums)+1)
        for k in range(1, len(pows)):
            pows[k] = (pows[k-1]<<1) % M
        ans = 0
        nums.sort()
        left = 0
        right = len(nums) - 1
        while left <= right:
            total = nums[left] + nums[right]
            if total > target:
                right -= 1
            else:
                ans = (ans + pows[right-left]) % M
                left += 1
        return ans
    '''
    
    def numSubseq(self, nums: List[int], target: int) -> int:
        M = 10**9 + 7
        pows = [1]*(len(nums)+1)
        for k in range(1, len(pows)):
            pows[k] = (pows[k-1]<<1) % M
        ans = 0
        nums.sort()
        base = 0
        for k in range(len(nums)):
            if nums[k]*2 <= target:
                ans += pow(2, k, M)
            else:
                while base > 0 and nums[base] + nums[k] > target:
                    base -= 1
                while base < k and nums[base] + nums[k] <= target:
                    base += 1
                ans += ((pow(2, base)-1) % M) * pow(2, k-base, M)
            #print(k, base, ans)
        return ans % M



class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        l = len(nums)
        left = 0
        right = l -1
        ans = 0
        while left <= right:
            curr = nums[left]
            leftover = target - curr
            if leftover < curr:
                return ans % (10 ** 9 + 7 )
            ans += 1
            while nums[right] > leftover:
                right -= 1
            ans += 2 ** (right - left) - 1
            left += 1
        return ans % (10 ** 9 + 7)
            
            


class Solution:
    def numSubseq(self, A: List[int], target: int) -> int:
        A.sort()
        l = 0
        r = len(A) - 1
        res = 0
        mod = 10 ** 9 + 7
        while l <= r:
            if A[l] + A[r] > target:
                r -= 1
            else:
                res += pow(2,r - l,mod)
                l += 1
        return res % mod

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        
        cnt = 0
        for i, n in enumerate(nums):
            if n+n>target:
                break
                    
            if n+nums[-1]<=target:
                R = len(nums)
                cnt += 2**(R-i-1)
                continue
            
            L = i
            R = len(nums)-1
            while L<R:
                mid = L+(R-L)//2
                if n+nums[mid]<=target:
                    L = mid+1
                else:
                    R = mid
            cnt += 2**(R-i-1)
            # print (n, i, R, cnt)
        return cnt%(10**9+7)


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        if not nums:
            return 0
        nums.sort()
        result = 0
        left = 0
        right = len(nums) - 1
        while left <= right:
            if nums[left] + nums[right] <= target:
                result += 2**(right - left)
                left += 1
            else:
                right -= 1
        return result % (10 ** 9 + 7)

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        j = len(nums)-1
        flag = False
        ans = 0
        for i in range(len(nums)):
            if flag:
                if nums[i]*2 > target:
                    break
                ans += 1
                
            else:
                while j>=i and nums[j]+nums[i] > target:
                    j -= 1

                if j>i:
                    ans += 2**(j-i)
                else:
                    if nums[i]*2 > target:
                        break
                    ans += 1
                    flag = True
                         
        return ans%(10**9 + 7)

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums = sorted(nums)
        res = 0
        i1, i2 = 0, len(nums) - 1
        while i1 <= i2:
            if nums[i1] + nums[i2] <= target:
                res += 2**(i2-i1)
                i1 += 1
            else:
                i2 -= 1
        return res % (10**9 + 7)



import math

class Solution:
    
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        left, right = 0, len(nums) - 1
        res = 0
        md = 10**9+7
        
        while left <= right:
            if nums[left] + nums[right] <= target:
               
                res += pow(2, right - left) 
                left += 1
            else:
                right -= 1
        return res % md

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        N = len(nums)
        nums.sort()
        ans =  0
        l, r = 0, N-1
        
        while l <= r:
            if nums[l] + nums[r] > target:
                r -= 1
            else:
                ans += 2**(r-l)
                l += 1
        
        return ans % (10**9 + 7)

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        mod = 10 ** 9 + 7
        nums.sort()
        left = 0
        right = len(nums) - 1
        ans = 0
        while left <= right:
            if nums[left] + nums[right] > target:
                right -= 1
            else:
                ans += 2 ** (right - left)
                left += 1
        return ans % mod
                


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        l = count = 0
        r = len(nums) - 1
        while l <= r:
            if nums[l] + nums[r] > target:
                r -= 1
            else:    
                count += 2 ** (r - l)
                l += 1
        return count % (10 ** 9 + 7)
            
            
             
            


import math

class Solution:
    
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        left, right = 0, len(nums) - 1
        res = 0
        md = 10**9+7
        
        #print(nums)
        
        while left <= right:
            if nums[left] + nums[right] <= target:
                res += pow(2, right - left) 
                left += 1
            else:
                right -= 1
        return res % md

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        
        cnt = 0
        for i, n in enumerate(nums):
            if i<len(nums)-1:
                if n+n>target:
                    continue
            else:
                if n+n>target:
                    continue
                    
#             print ('ssss')
                    
            if n+nums[-1]<=target:
                R = len(nums)
                cnt += 2**(R-i-1)
                continue
            
            L = i
            R = len(nums)-1
            while L<R:
                mid = L+(R-L)//2
                if n+nums[mid]<=target:
                    L = mid+1
                else:
                    R = mid
            cnt += 2**(R-i-1)
            # print (n, i, R, cnt)
        return cnt%(10**9+7)


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        # print(nums, len(nums))
        count = 0
        j = len(nums)-1
        
        for i in range(len(nums)):
            while (nums[i]+nums[j]>target) & (i<j):
                j -= 1
            
            if (i>j) | (nums[i]*2>target) :
                break
            # print(j-i, end=' & ')
            count += 2**(j-i)
            # count = count

        return count%(10**9+7)


class Solution:
    def numSubseq(self, A: List[int], t: int) -> int:
        A, n = sorted(A), len(A)
        mod = (10 ** 9 + 7)
        ret = 0
        left, right = 0, n - 1
        while left <= right:
            while right >= left and A[left] + A[right] > t:
                right -= 1
            if right >= left and A[left] + A[right] <= t:
                ret += 2 ** (right - left)
            left += 1
        return ret % mod

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        ans, i, j = 0, 0, len(nums) - 1
        while i <= j:
            if nums[i] + nums[j] <= target:
                ans += 2 ** (j - i)
                i += 1
            else:
                j -= 1
        return ans % (10 ** 9 + 7)

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        l=0
        r=len(nums)-1
        res=0
        mod=10**9+7
        while l<=r:
            if nums[l]+nums[r]>target:
                r-=1
            else:
                res+=pow(2,r-l)
                l+=1
        return res%mod

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        print(nums)
        l, r = 0, len(nums) - 1
        res = 0
        while l <= r:
            if nums[l] + nums[r] > target:
                r -= 1
            else:
                res += 2 ** (r - l)
                l += 1
        return res % (10 ** 9 + 7)
            


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        mod = 10 ** 9 + 7
        left, right = 0, len(nums) - 1
        res = 0
        while left <= right:
            if nums[left] + nums[right] > target:
                right -= 1
            else:
                res += pow(2, right - left)
                left += 1
        return res % mod


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums = sorted(nums)
        i, j = 0, len(nums) - 1
        res = 0
        while i <= j:
            while i <= j and nums[i] + nums[j] > target:
                j -= 1
            if i <= j and nums[i] + nums[j] <= target:
                res += 2 ** (j - i)
            i += 1
        return res % (10 ** 9 + 7)

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        N = len(nums)
        nums.sort()
        res = 0
        left, right = 0, N - 1
        while left <= right:
            if nums[left] + nums[right] > target:
                right -= 1
            else:
                res += 2 ** (right-left)
                left += 1
        return res % (10**9+7)

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        idx, res = len(nums)-1, 0
        nums.sort()
        for i in range(len(nums)):
            while nums[i]+ nums[idx]> target and idx>=i:
                idx-=1
            if idx< i:
                break
            res += 2 ** (idx-i)
            
        return res%(10**9+7)

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1
        output, nums = 0, sorted(nums)
        while l <= r:
            if nums[l] + nums[r] <= target:
                output += pow(2, r - l)
                l += 1
            else:
                r -= 1
        return output % (10 ** 9 + 7)
    
    # def numSubseq(self, A, target):
    #     A.sort()
    #     l, r = 0, len(A) - 1
    #     res = 0
    #     mod = 10**9 + 7
    #     while l <= r:
    #         if A[l] + A[r] > target:
    #             r -= 1
    #         else:
    #             res += pow(2, r - l, mod)
    #             l += 1
    #     return res % mod


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        lo, hi, ans = 0, len(nums) - 1, 0
        while lo <= hi:
            if nums[lo] + nums[hi] > target:
                hi -= 1
                continue
            ans += 2 ** (hi - lo)
            lo += 1
        return ans % (10**9 + 7)


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        start = 0
        end = len(nums)-1
        ans = 0
        mod = 10**9 + 7
        
        while start<=end:
            while nums[start]+nums[end]>target:
                end -= 1
                if start>end:
                    return ans%mod
            
            ans += 2**(end-start)
            start += 1
            
        return ans%mod
        
        


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        m = 10 ** 9 + 7
        l = 0
        r = len(nums) - 1
        res = 0
        
        while l <= r:
            while l <= r and nums[l] + nums[r] > target:
                r -= 1
            if l <= r:
                res += 2 ** (r - l)
                l += 1
            else:
                break
        return res % m

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        l,r=0,len(nums)-1
        re=0
        while l<=r:
            while r>=l and nums[l]+nums[r]>target:
                r-=1
            if r<l:
                break
            re+=2**(r-l)
            l+=1
        return re%1000000007
        


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        # print(nums, len(nums))
        count = 0
        j = len(nums)-1
        
        for i in range(len(nums)):
            while (nums[i]+nums[j]>target) & (i<j):
                j -= 1
            
            if (i>j) | (nums[i]*2>target) :
                break
            # print(j-i, end=' & ')
            count += pow(2, j-i)
            # count = count

        return count%(10**9+7)


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        count = 0
        nums.sort()
        left, right = 0, len(nums)-1
        
        while left <= right:
            x0 = nums[left]
            if x0 + nums[right] > target:
                right -= 1
                continue
            
            count += 2**(right-left)
            left += 1
            
        return count % (10 ** 9 + 7)

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        left, right = 0, len(nums) - 1
        count = 0
        while left <= right:
            if nums[left] + nums[right] <= target:
                count += 2**(right - left)
                left += 1
            else:
                right -= 1
        return count % (10**9 + 7)

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        low = 0
        high = len(nums)-1
        total = 0
        while low < len(nums):
            while high > low and nums[low] + nums[high] > target:
                high -= 1
            s = nums[low] + nums[high]
            if s > target:
                break
            total += 2 ** (high - low)
            low += 1
            high = max(high, low)
        return total % (10 ** 9 + 7)             


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        if not nums:
            return 0
        
        nums.sort()
        res = 0
        lo, hi = 0, len(nums)-1
        
        while lo <= hi:
            if nums[lo]+nums[hi] > target:
                hi -= 1
            else:
                res += pow(2, hi-lo)
                lo += 1
        
        return res % (pow(10,9)+7)

from collections import Counter
class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        c = Counter(nums)
        nums = []
        for k, v in sorted(list(c.items()), key=lambda x:x[0]):
            nums.extend([k]*v)
        res = 0
        i1, i2 = 0, len(nums) - 1
        while i1 <= i2:
            if nums[i1] + nums[i2] <= target:
                res += 2**(i2-i1)
                i1 += 1
            else:
                i2 -= 1
        return res % (10**9 + 7)



class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums = sorted(nums)

        left = 0
        right = len(nums) - 1

        result = 0

        while True:

            while left <= right and (nums[left] + nums[right] > target):
                right -= 1

            if right < left:
                break

            print((left, right))
            result += pow(2, right - left)

            left += 1

        return result % (10**9 + 7)
        


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums = sorted(nums)

        left = 0
        right = 0

        while right < len(nums) and (nums[left] + nums[right] <= target):
            right += 1

        right -= 1

        result = 0

        while True:

            while left <= right and (nums[left] + nums[right] > target):
                right -= 1

            if right < left:
                break

            print((left, right))
            result += pow(2, right - left)

            left += 1

        return result % (10**9 + 7)
        


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        print(nums, len(nums))
        count = 0
        j = len(nums)-1
        
        for i in range(len(nums)):
            while (nums[i]+nums[j]>target) & (i<j):
                j -= 1
            
            if (i>j) | (nums[i]*2>target) :
                break
            print(j-i, end=' & ')
            count += 2**(j-i)
        
        print(i, j)
        return count%(10**9+7)
            

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        left = 0
        right = len(nums)-1
        mod = (10**9) + 7
        out = 0
        while left<=right:
            if nums[left]+nums[right] > target:
                right -= 1
            elif nums[left]+nums[right]<=target:
                space = right-left
                out += pow(2, space)
                left += 1
             
               
        return out%mod        

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        i=0
        count=0
        j=len(nums)-1
        while i<len(nums) and nums[i]*2<=target:
            #count+=1
            while i<j and nums[i]+nums[j]>target:
                j-=1
                
            #print(i,j,nums[i],nums[j])
            count+=2**(j-i)
            i+=1
        return count%(10**9+7)

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        n = len(nums)
        module = 10 ** 9 + 7
        ret = 0
        lo, hi = 0, n - 1
        while lo <= hi:
            if nums[lo] + nums[hi] > target:
                hi -= 1
            else:
                ret += 1 << (hi - lo)
                lo += 1
        return ret % module

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        i = 0 
        j = len(nums) - 1
        count = 0
        mod = 10 ** 9 + 7
        nums.sort()
        while i < len(nums) and j < len(nums):
            while nums[j] + nums[i] > target and i <= j:
                j -= 1
            
            if nums[j] + nums[i] <= target and i <= j:
                count += 2 ** (j - i)
            
            i += 1
        
        return int(count % mod)

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        N = len(nums)
        nums.sort()
        answer = 0
        for i in range(N):
            current_num = nums[i]
            low = i + 1
            high = N-1
            while low <= high:  
                middle = (low + high)//2
                if current_num + nums[middle] > target:
                    high = middle - 1
                else:
                    low = middle + 1

            if current_num + nums[high] <= target:
                answer += (2 ** (high - i))

        return answer % ((10**9) + 7)

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        right = len(nums) - 1
        left = 0
        ret = 0
        
        
        while (left < right):   
            if (nums[left] * 2 <= target):
                ret += 1
            
            max_right = target - nums[left]
            
            
            while (left < right and max_right < nums[right]):  
                if (nums[right] * 2 <= target):
                    ret += 1
                    
                right -= 1

                
            if (left < right):  
                ret += 2 ** (right - left) - 1
            else:
                return ret % 1000000007 
                
            left += 1
       
        
        if (nums[right] * 2 <= target):
            ret += 1
            
        return ret % 1000000007 

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        right = len(nums) - 1
        left = 0
        ret = 0
        
        
        while (left < right):   
            max_right = target - nums[left]
            
            
            while (left < right and max_right < nums[right]):   
                right -= 1

                
            if (left < right):  
                ret += 2 ** (right - left) - 1
                
            left += 1
                
                
        for i in range(len(nums)):
            if (nums[i] * 2 > target):
                break
                
            ret += 1
        
        return ret % 1000000007     


class Solution:
    def numSubseq(self, x: List[int], t: int) -> int:
        def bi(lo,hi,val):
            while lo<=hi:
                m=(lo+hi)//2
                if x[m]<=val:
                    lo=m+1
                else:hi=m-1
            return lo-1
        x.sort()
        l=len(x)
        ans=0
        for i in range(l):
            if t-x[i]>=x[i]:
                ind=bi(i,l-1,t-x[i])
                ans+=2**(ind-i)
            else:break
        return ans%(10**9+7)

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        ans = 0
        nums.sort()
        for i in range(len(nums)):
            if nums[i]*2 > target:
                break
            l, r = i, len(nums)-1
            while l+1 < r:
                mid = (l+r)//2
                if nums[i] + nums[mid] > target:
                    r = mid
                else:
                    l = mid
            if nums[i] + nums[r] <= target:
                ind = r
            else:
                ind = l
            ans += 2**(ind-i)
        return ans%(10**9+7)


#3:56

class Solution:
    def find_endindex(self, nums, ind, target):
        start = ind
        end = len(nums) -1
        
        while start < end:
            mid = (start + end)//2
            if nums[mid] + nums[ind] > target:
                end = mid
            else:
                start = mid + 1
                
        if nums[start] + nums[ind] > target:
            start -= 1
        
        #if start >= ind:
        return 2**(start - ind)
        #else:
        #    return 0
        
        
        
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums2 = sorted(nums)
        result = 0
        if nums2[0] > target:
            return result
        
        for i in range(len(nums2)):
            if nums2[i]*2 <= target:
                res = self.find_endindex(nums2, i, target)
                #print (i, res)
                result += res
            else:
                break
            
        return result%(10**9 + 7)


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        # sort first
        nums.sort()
        
        # sliding windows        
        n = len(nums)
        res = 0
        
        #one length subsequence
        mod = 10**9 + 7
        i,j = 0,n-1
        
        # -> <-
        
        # i: min start, move -> 
        for i in range(n):  
            # j: max, move <- until we find the boundary
            while j>=i and nums[i]+nums[j] > target:
                j -= 1 
            # anything in between [i,j] is answer. You always have i as _min + subsets of (j-i) would be answer. # combo = 2^(j-i)      
            if i<=j and nums[i] + nums[j] <= target:
                res += pow(2,(j-i) , mod)
                res %= mod
        
        return res

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        MOD = 10**9 + 7
        nums.sort()
        result = 0
        for i in range(len(nums)):
            if nums[i] <= target // 2:
                left, right = i, len(nums) - 1
                while left < right - 1:
                    mid = (left + right) //  2
                    if nums[mid] <= target - nums[i]:
                        left = mid
                    else:
                        right = mid - 1
                if nums[i] + nums[right] <= target:
                    result += 2**(right - i)
                elif nums[i] + nums[left] <= target:
                    result += 2**(left - i)
        return result % MOD
                    
                    


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        
        count = 0
        
        nums.sort()
        
        # print(nums)
        
        for i in range(len(nums)):
            
            if (nums[i] * 2) > target:
                
                break
            
            left = i
        
            right = len(nums) - 1
            
            while left < right:
            
                mid = (left + right + 1) // 2

                if nums[i] + nums[mid] <= target:

                    left = mid

                else:

                    right = mid - 1
                    
            # print(nums[i], nums[left])
                    
            count += (2 ** (left - i))
                
        return count % (10 ** 9 + 7)

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        N = len(nums)
        ans = 0
        rgt = N-1
        for lft in range(N):
            # min is nums[lft]
            if nums[lft] * 2 > target:
                break
                
            # Find the largest rgt such that nums[lft] + nums[rgt] > target
            lo, hi = lft, N-1
            while lo + 1 < hi:
                m = (lo + hi)//2
                if nums[lft] + nums[m] <= target:
                    lo = m
                else:
                    hi = m

            # typically f[lo] <= target < f[hi]
            # f[hi] <= target is possible
            # f[lo] > target is impossible
            if nums[lft] + nums[hi] > target:
                ans += 2**(lo-lft)
            else:
                ans += 2**(hi-lft)
                
        return ans % (10**9 + 7)

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        if len(nums) == 0:
            return 0
        nums.sort()
        result = 0
        for start in range(len(nums)):
            left, right = start, len(nums) - 1
            while left < right - 1:
                mid = (left + right) // 2
                if nums[mid] > target - nums[start]:
                    right = mid - 1
                else:
                    left = mid
            if nums[start] + nums[right] <= target:
                end = right
            elif nums[start] + nums[left] <= target:
                end = left
            elif nums[start] + nums[start] <= target:
                end = start
            else:
                end = -1
            if end > start:
                result += 2 ** (end-start)
            if end == start:
                result += 1
            #print(start, end, result)
        return result % (10**9+7)
                
                


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        res = 0
        l = 0
        r = len(nums) - 1
        mod = 10 ** 9 + 7
        while l <= r:                       ##min和max值可以相等！！
            if nums[l] + nums[r] > target:
                r -= 1
            else:
                res += 2 ** (r - l) % mod
                l += 1                  ##这个开头的最大值！！
        return res % mod
        


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        n=len(nums)
        p=[1]*(n+1)
        for i in range(1,n+1):
            p[i]=p[i-1]<<1
        nums.sort()
        res=0
        j=n-1
        for i in range(j+1):
            #固定起始i找最右端点
            while i<=j and nums[i]+nums[j]>target:
                j-=1
            if i>j:
                continue
            #此时i--j之间子序列都可以，
            #只要最小值为第i项
            '''
            In subarray nums[i~j]:
            min = nums[i], max = nums[j]
            nums[i] + nums[j] <= target
            {nums[i], (j - i - 1 + 1 values)}
            Any subset of the right part gives a valid subsequence 
            in the original array. And There are 2^(j - i) ones.
            '''
            res+=2**(j-i)
        return res%(10**9+7)

class Solution:
    MOD = 10**9 + 7

    def numSubseq(self, nums: List[int], target: int) -> int:
        n = len(nums)
        nums.sort()
        
        count = 0
        i, j = 0, n - 1
        while i <= j:
            if nums[i] + nums[j] > target:
                j -= 1
                
                continue

            len_ = j - i + 1
            count += (2**(len_ - 1)) % self.__class__.MOD
                
            i += 1
                    
        return count % self.__class__.MOD


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        l, r = 0, len(nums) - 1
        res = 0
        mod = (10**9+7)
        while l <= r:
            if nums[l] + nums[r] > target:
                r -= 1
            else:
                res += 2 ** (r - l) % mod
                l += 1
        return res % (10**9+7)

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums = sorted(nums)
        result = 0
        l, r = 0, len(nums) - 1
        while l <= r:
            if nums[l] + nums[r] > target:
                r -= 1
            else:
                result = (result + 2 ** (r-l)) % (10**9 + 7)
                l += 1
                
        return result

class Solution:
  def numSubseq(self, nums: List[int], target: int) -> int:
    nums.sort()
    n = len(nums)
    i, j, count = 0, n - 1, 0
    while i <= j:
      while i <= j and nums[i] + nums[j] > target:
        j -= 1
      if i <= j:
        # nums[i] be the min, any combinations of nums[(i+1):(j+1)]
        count += 1 << (j - i)
      i += 1
    return count % (10 ** 9 + 7)

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums = sorted(nums)
        result = 0
        mod = 10 ** 9 + 7
        l, r = 0, len(nums) - 1
        while l <= r:
            if nums[l] + nums[r] > target:
                r -= 1
            else:
                result = (result + 2 ** (r-l)) % mod
                l += 1
                
        return result

max_cap = 7 + (10 ** 9)

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        init_seq_len = len(nums)
        nums.sort()

        l = 0
        r = init_seq_len - 1
        count = 0
        while (l <= r):
            if nums[l] + nums[r] > target:
                r -= 1
            else:
                count += (2 ** (r - l) % max_cap)
                l += 1
        return (count % max_cap)

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        
        if not nums or target == 0 :
            return 0
        
        
        nums.sort()
        
        l, r = 0, len(nums) -1 
        mod = 10**9 + 7
        res = 0
        while l <= r:
            if nums[l] + nums[r] > target:
                r -= 1
            else:
                res += (2**(r-l))%mod
                l += 1
        return res%mod

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        i = 0
        j = len(nums)-1
        s = 0
        while i<=j:
            if nums[i]+nums[j] <= target:
                s = (s + 2**(j-i))%(10**9 + 7)
                i += 1
            else:
                j -= 1
        return s

MOD = 1000000007
class Solution:
    def numSubseq(self, nums, target):
        if not nums:
            return 0
        nums = sorted(nums)
        n = len(nums)
        left, right = 0, n - 1
        res = 0
        while left <= right:
            if nums[left] + nums[right] <= target:
                res += 2 ** (right - left) 
                res %= MOD
                left += 1
            else:
                right -= 1
        return res % MOD

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        MOD = 10**9 + 7
        
        i, j , ans = 0, len(nums)-1, 0
        while i<=j:
            if nums[i]+nums[j]<=target:
                ans+=(2**(j-i))%MOD
                i+=1
            else:
                j-=1
        
        return ans%MOD
            
            


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        l, r = 0, len(nums) - 1
        ans, mod = 0, 10 ** 9 + 7
        while l <= r:
            if nums[l] + nums[r] <= target:
                ans = (ans + 2 ** (r - l)) % mod
                l += 1
            else:
                r -= 1
        return ans

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums = sorted(nums)
        n = len(nums)
        count = 0
        i, j = 0, n-1
        while i <= j:
            tot = nums[i] + nums[j]
            if tot <= target:
                count += 2**(j-i) % int(1e9 + 7)
                i += 1
            else:
                j -= 1
         
        return int(count % (1e9 + 7))

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        if not nums:
            return 0
        
        nums.sort()
        
        MOD = 10 ** 9 + 7
        
        res = 0
        i = 0
        j = len(nums) - 1
        
        for i in range(len(nums)):
            while i <= j and nums[i] + nums[j] > target:
                j -= 1
                
            if i <= j and nums[i] + nums[j] <= target:
                res = (res + 2 ** (j - i)) % MOD
    
            i += 1
            
        return res

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        n = len(nums)
        total = 0
        right = n - 1
        for i in range(len(nums)):
            if nums[i] > target or right < i:
                break
            while right >= i and nums[i] + nums[right] > target:
                right -= 1
            if right < i:
                break
            if nums[i] + nums[right] <= target:
                total = (total + 2 **(right - i)) % (10**9 + 7)
             
        return int(total) % (10**9 + 7)


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        n = len(nums)
        res = 0
        #one length subsequence
        mod = 10**9 + 7
        i,j = 0,n-1
        
        
        for i in range(n):
            while i<=j and nums[i]+nums[j] > target:
                j-=1
            
            if i<=j and nums[i] + nums[j] <= target:
                res += pow(2, j - i)
                res %= mod
        
        return res


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        if not nums:
            return 0
        
        nums.sort()
        
        MOD = 10 ** 9 + 7
        
        res = 0
        i = 0
        j = len(nums) - 1
        
        h = dict()
        
        while i < len(nums):
            while i <= j and nums[i] + nums[j] > target:
                j -= 1
                
            if i <= j and nums[i] + nums[j] <= target:
                
                if j-i not in h:
                    h[j-i] = 2 ** (j - i)
                
                res = (res + h[j-i]) % MOD
    
            i += 1
        
            if i > j:
                break
            
        return res

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        sorted_nums = sorted(nums)
        res = 0
        mod = (10**9+7)
        r = len(sorted_nums)-1
        for i,left in enumerate(sorted_nums):
            while left+sorted_nums[r] > target and i<=r:
                r-=1
            if i<=r:
                res+=(2**(r-i))
                res%=mod
        return res


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        if not nums:
            return 0
        
        nums.sort()
        
        MOD = 10 ** 9 + 7
        
        res = 0
        i = 0
        j = len(nums) - 1
        
        while i < len(nums):
            while i <= j and nums[i] + nums[j] > target:
                j -= 1
                
            if i <= j and nums[i] + nums[j] <= target:
                res = (res + 2 ** (j - i)) % MOD
    
            i += 1
        
            if i > j:
                break
            
        return res

# if a .... b , where a<=b<=target
#the # of subsquence starts with a = 2^(n-1), where n is len([a...b])

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        l = 0
        r = len(nums)-1
        res = 0
        nums.sort()
        M = 10**9+7
        while l<=r:
            if nums[l] + nums[r] <= target:
                res = (res + pow(2,r-l,M))%M
                l+=1
            else:
                r-=1
        return res

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        
        n, res, mod, j = len(nums), 0, 10**9 + 7, len(nums) - 1
        
        for i in range(n):
            while i <= j and nums[i] + nums[j] > target:
                j -= 1
            
            if i <= j and nums[i] + nums[j] <= target:
                res += 2**(j-i) % mod
                res %= mod
        return res

class Solution:
    def numSubseq(self, nums, target: int) -> int:

        n = len(nums)
        nums.sort()
        res = 0
        i = 0
        last = n-1
        while i<n and 2*nums[i]<=target:
            j = last
            while j>=i and nums[i]+nums[j]>target:
                j -= 1
            last = j
            if i == j:
                res += 1
            else:
                res += 2**(j-i)   %1000000007
            i += 1
        return res%1000000007

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        l, r = 0, len(nums)-1
        res, mod = 0, 10**9+7
        while l<=r:
            sum_ = nums[l]+nums[r]
            if sum_ <= target:
                res += (2**(r - l))%mod
                l += 1
            else:
                r -= 1
        return res % mod

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        
        i, j = 0, len(nums) - 1
        res = 0
        
        while i <= j:
            if nums[i] + nums[j] > target:
                j -= 1
            else:
                res = (res + 2 ** (j - i)) % (10 ** 9 + 7)  # 除去左边界的元素（因为要固定它作为min），对于它右边的所有元素，都有选和不选两种可能，所以是2^N，N是右边元素数量
                i += 1
        
        return res

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        l, r = 0, len(nums) - 1
        res = 0
        while l <= r:
            if nums[l] + nums[r] > target:
                r -= 1
            else:
                res += 2 ** (r - l) % (10 ** 9 + 7)
                l += 1
        return res % (10 ** 9 + 7)
            


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums = sorted(nums)
        i, j = 0, len(nums) - 1
        ans  = 0
        while i <= j:
            if nums[i] + nums[j] <= target:
                ans += 2**(j-i) % (10**9 + 7)
                i += 1
            else:
                j -= 1
        return ans % (10**9 + 7)
        


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        '''
        Sort the array and grab min and max elements such that nums[min] + nums[max] <= target
        Now in the substring nums[min : max]
            min can be always selected and all combinations in [min + 1 to max] can be tried which would result in the substring having min = min and max <= max resulting in max - min <= target
        This selection yields 2^(max - min) possibilities
        '''
        
        nums.sort()
        n = len(nums)
        res = 0
        #one length subsequence
        mod = 10**9 + 7
        i,j = 0,n-1
        
        
        for i in range(n):
            while i<=j and nums[i]+nums[j] > target:
                print((nums[i], nums[j]))
                j-=1
            
            if i<=j and nums[i] + nums[j] <= target:
                res += pow(2, j - i)
                res %= mod
                print((nums[i], i, nums[j], j, res))
        
        return res


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        l = count = 0
        r = len(nums) - 1
        mod = (10 ** 9 + 7)
        while l <= r:
            if nums[l] + nums[r] > target:
                r -= 1
            else:    
                count += (2 ** (r - l)) % mod
                l += 1
        return count % mod
            
            
             
            


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        l=0
        n=len(nums)
        r=n-1 
        mod=10**9+7
        c=0
        
        while(l<=r):
            if nums[l]+nums[r]>target:
                r-=1 
            else:
                c=(c+((2**(r-l))%mod))%mod
                l+=1 
        return c

class Solution:
    def numSubseq(self, nums, target: int) -> int:

        n = len(nums)
        nums.sort()
        res = 0
        mod = 10**9+7
        last = n-1
        t=target/2
        
        f = [1] + [0] * (n - 1)
        for i in range(1, n):
            f[i] = f[i - 1] * 2 % mod
            
        i = 0
        while i<n and nums[i]<=t:
            j = last
            while j>=i and nums[i]+nums[j]>target:
                j -= 1
            last = j
            res += f[j-i]
            i += 1
        return res%1000000007

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        # Number of sebsequences that satisfy given sum
        # 10:50 9/10/20
        
        def find_right(nums, j, target): # len(nums)
            if j == 1:
                return j-1
            i = 0
            while i < j:
                mid = i + (j - i) // 2
                if nums[mid] + nums[0] > target:
                    j = mid
                else:
                    i = mid + 1
            return i - 1
        
        
        n = len(nums)
        nums.sort()
        left = 0
        right = find_right(nums, len(nums), target)
        MOD = 10**9 + 7
        res = 0
        
        
        while left <= right:
            if nums[left] + nums[right] <= target:
                # res += (2**(right - left + 1)-1) % MOD
                res = (res + pow(2, right-left)) % MOD
                left += 1
            else:
                right -= 1
        
        return res
    
    
    
        # n,result,p1,p2,m=len(nums),0,0,len(nums)-1,1000000007
        # nums.sort()
        # while(p1<=p2):
        #     if nums[p1]+nums[p2]<=target:
        #         result=(result+pow(2,p2-p1,m))%m
        #         p1+=1
        #     else:
        #         p2-=1
        # return result
                
    
    
    
    
 
        


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        l,r=0,len(nums)-1
        cnt=0
        mod=pow(10,9)+7
        while(l<=r):
            if(nums[l]+nums[r]>target):
                r-=1
            else:
                cnt+=pow(2,r-l)
                cnt=cnt%mod
                l+=1
                
        return cnt

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        res = 0
        j = len(nums)-1
        mod = 10**9+7
        
        for i in range(len(nums)):
            if nums[i]>target:
                break
            while j>=i and nums[i]+nums[j]>target:
                j-=1
            if j<i:
                break
            if i==j:
                res+=1
                continue
            n = j-i
            res += (2**n)%mod
        return res%mod
                


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        left, right = 0, len(nums) - 1
        res = 0
        mod = 10**9 + 7
        while left <= right:
            if nums[left] + nums[right] > target:
                right -= 1
            else:
                res += 2 ** (right - left) % mod
                left += 1

        return res % mod

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        mod=(10**9)+7
        right=len(nums)-1
        res=0
        left=0
        while left<=right:
            if nums[left]+nums[right]>target:
                right-=1
            else:
                res+=2**(right-left)
                res=res%mod
                left+=1
            
        return res


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums=sorted(nums)
        c=10**9+7
        left=0
        res=0
        right=len(nums)-1
        while(left<=right):
            if nums[left]+nums[right]<=target:
                res=(res+pow(2,(right-left)))%c
                left+=1
            else:
                right-=1
        return res        
                


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        MOD = 10 ** 9 + 7
        nums.sort()
        right = len(nums) - 1
        count = 0
        # pow2 = [0 for _ in range(len(nums))]
        # pow2[0] = 1
        # for i in range(len(pow2)):
        #     if i>0:
        #         pow2[i] = (pow2[i-1] * 2) % MOD
        for i in range(len(nums)):
            while right>=i and nums[i] + nums[right] > target:
                right -= 1
            if right < i:
                break
            else:
                # count += pow2[right - i]
                count += 2 ** (right - i)
            count %= MOD
        return count % MOD


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        l = 0
        r = len(nums) - 1
        result = 0
        mod = pow(10, 9) + 7
        
        while l <= r:
            if nums[l] + nums[r] > target:
                r -= 1
            else:
                result += pow(2, r-l, mod)
                l += 1
        return result % mod

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        res = 0
        j = len(nums) - 1
        i = 0
        while i <= j:
            if nums[i] + nums[j] > target:
                j -= 1
            else:
                res += 2**(j-i) % (10**9 + 7)
                i += 1
        
        return res % (10**9 + 7)
        


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        i, j, res, N = 0, len(nums) - 1, 0, 10 ** 9 + 7
        nums.sort()
        
        while i <= j:
            if nums[i] + nums[j] > target: j -= 1
            else:
                res += (2 ** (j - i)) % N
                i += 1
        return res % N


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        MOD = 10**9 + 7
        nums.sort()
        for ri in range(len(nums)):
            if nums[ri] + nums[0] > target:
                break
        
        le, ans = 0, 0
        while le <= ri:
            if nums[le] + nums[ri] > target:
                ri -= 1
            else:
                cnt = 2**(ri - le)
                ans = (ans+cnt)%MOD
                le += 1
        return ans
                


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        start = 0 
        end = len(nums)-1
        
        count = 0
        while start <= end:
            if nums[start] + nums[end] > target:
                end -= 1
            else:
                num_in_between = end - start 
                count += 2**num_in_between
                count %= (10**9 + 7)
                start += 1
                
        return count


class Solution:
    def numSubseq(self, A: List[int], t: int) -> int:
        A, n = sorted(A), len(A)
        mod = (10 ** 9 + 7)
        ret = 0
        left, right = 0, n - 1
        while left <= right:
            while right >= left and A[left] + A[right] > t:
                right -= 1
            if right >= left and A[left] + A[right] <= t:
                ret += 2 ** (right - left) % mod
            left += 1
        return ret % mod

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        sn = sorted(nums)
        ans = 0
        mod = 1000000007
        l = 0
        r = len(nums) - 1
        while l <= r:
            if sn[l] + sn[r] > target:
                r -= 1
                continue
            u = int(pow(2, r - l))
            ans = (ans + u) % mod
            l += 1

        return ans

class Solution:
    def numSubseq(self, A: List[int], t: int) -> int:
        A, n = sorted(A), len(A)
        mod = (10 ** 9 + 7)
        ret = 0
        left, right = 0, n - 1
        while left <= right:
            while right >= left and A[left] + A[right] > t:
                right -= 1
            if right >= left and A[left] + A[right] <= t:
                ret += 2 ** (right - left) % mod
                ret %= mod
            left += 1
        return ret % mod

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        # print(nums, len(nums))
        count = 0
        j = len(nums)-1
        
        for i in range(len(nums)):
            while (nums[i]+nums[j]>target) & (i<j):
                j -= 1
            
            if (i>j) | (nums[i]*2>target) :
                break
            # print(j-i, end=' & ')
            count += 2**(j-i)
            count = count%(10**9+7)

        return count


class Solution:
    def numSubseq(self, A: List[int], target: int) -> int:
        A.sort()
        l, r = 0, len(A) - 1
        res = 0
        mod = 10**9 + 7
        while l <= r:
            if A[l] + A[r] > target:
                r -= 1
            else:
                res += pow(2, r - l, mod)
                l += 1
        return res % mod
#         i, j, res, N = 0, len(nums) - 1, 0, 10 ** 9 + 7
#         nums.sort()
        
#         while i <= j:
#             if nums[i] + nums[j] > target: j -= 1
#             else:
#                 res += (2 ** (j - i)) % N
#                 i += 1
#         return res % N


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        MOD = 10**9 + 7
        nums.sort()
        for ri in range(len(nums)):
            if nums[ri] + nums[0] > target:
                break
        le, ans = 0, 0
        while le <= ri:
            if nums[le] + nums[ri] > target:
                ri -= 1
            else:
                ans = (ans + 2**(ri-le)) % MOD
                le += 1
        return ans


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        '''
        Sort (nlogn) the array [as opposed to using DP ~= typically n^2 and complex in this case] and grab min and max elements such that nums[min] + nums[max] <= target
        Now in the substring nums[min : max]
            min can be always selected and all combinations in [min + 1 to max] can be tried which would result in the substring having min = min and max <= max resulting in max - min <= target
        This selection yields 2^(max - min) possibilities
        '''
        
        nums.sort()
        n = len(nums)
        res = 0
        #one length subsequence
        mod = 10**9 + 7
        i,j = 0,n-1
        
        
        for i in range(n):
            while i<=j and nums[i]+nums[j] > target:
                print((nums[i], nums[j]))
                j-=1
            
            if i<=j and nums[i] + nums[j] <= target:
                res += pow(2, j - i)
                res %= mod
                print((nums[i], i, nums[j], j, res))
        
        return res


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums = sorted(nums)
        left, right = 0, len(nums)-1
        ans = 0
        mod = 10**9+7
        while left<=right:
            if nums[left] + nums[right] > target:
                right -= 1
            else:
                ans = (ans + 2**(right-left)) % mod
                left += 1
        
        return ans

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        res = left = 0
        right = len(nums)-1
        while(left<=right):
            if nums[left] + nums[right]<=target:
                res = (res + 2**(right-left)) % (10**9 + 7)
                left += 1
            else:
                right -= 1
        return res 


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        start,end=0,len(nums)-1
        res=0
        mod = 10**9 + 7
        while start<=end:
            if nums[start]+nums[end]>target:
                end-=1
            else:
                res+=pow(2,end-start)%mod
                start+=1
        return res%mod
                


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums = sorted(nums)
        
        left, right = 0, len(nums)-1
        
        ans = 0
        mod = 10**9+7
        while left<=right:
            if nums[left] + nums[right] > target:
                right -= 1
                continue
            else:
                ans = (ans + 2**(right-left)) % mod
                left += 1
        
        return ans

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        start=0
        end=len(nums)-1
        count=0
        while(start<=end):
            if((nums[start]+nums[end])<=target):
                count+=2**(end-start)%1000000007
                start+=1
            else:
                end-=1
        for i in range(end+1,len(nums)):
            if(nums[i]*2<=target):
                count+=1
            else:
                break
        return count%1000000007

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        MOD = 10 ** 9 + 7
        nums.sort()
        right = len(nums) - 1
        count = 0
        for i in range(len(nums)):
            while right>i and nums[right] > target - nums[i]:
                right -= 1
            if right == i:
                if 2*nums[i]<=target:
                    count += 1
                return count % MOD
            else:
                count += 2 ** (right - i)
            count %= MOD
        return count % MOD


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        res = 0
        
        nums.sort()
        
        i = 0
        j = len(nums)-1
        
        while i <= j:
            if nums[i] + nums[j] > target:
                j -= 1
            else:
                res += pow(2, j-i)
                res %= 10**9+7
                i += 1
        
        return res

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        right=len(nums)-1
        res=0
        for i in range(len(nums)):
            while nums[i]+nums[right]>target and i<=right:
                right-=1
            if i<=right:
                res+=2**(right-i)
                res=res%((10**9)+7) 
        return res


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        l = count = 0
        r = len(nums) - 1
        mod = (10 ** 9 + 7)
        while l <= r:
            if nums[l] + nums[r] > target:
                r -= 1
            else:    
                count += pow(2, r - l, mod)
                l += 1
        return count % mod
            
            
             
            


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        A = sorted(nums)
        r = len(A)-1
        l = 0
        out = 0
        while l <= r:
            if target - A[r] - A[l] < 0:
                r -= 1
            else:
                out += (2**(r-l))%((10**9)+7)
                l += 1
        return out%((10**9)+7)


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        m = 10**9+7
        ans = 0
        i, j = 0, len(nums)-1
        nums.sort()
        pi, pj = -1, -1
        while (pi, pj) != (i, j):
            pi, pj = i, j
            while j > i and nums[i] + nums[j] > target:
                j -= 1

            while i <= j and nums[i] + nums[j] <= target:
                ans = (ans + 2**(j-i)) % m
                i += 1
        
        return ans

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        ans = 0
        i = 0
        j = len(nums)-1
        while i <= j:
            s = nums[i] + nums[j]
            if s <= target:
                ans += 2**(j - i)
                ans %= 10**9+7
                i += 1
            else:
                j -= 1
        return ans

MOD = 10**9 + 7

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        l, r = 0, len(nums) - 1
        res = 0
        
        while l <= r:
            if nums[l] + nums[r] > target:
                r -= 1
            else:
                res = (res + pow(2, r - l)) % MOD
                l += 1
                
        return res


MOD = 10 ** 9 + 7

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        N = len(nums)
        if N == 1:
            return 1 if nums[0] * 2 <= target else 0
        
        nums.sort()
        
        ret = 0
        start = 0
        end = N - 1
        
        while start + 1 < end:
            mid = start + (end - start) // 2
            if nums[mid] * 2 > target:
                end = mid
            else:
                start = mid
                
        if nums[end] * 2 > target:
            if nums[start] * 2 > target:
                return 0
            ret += end
        else:
            return (2 ** (end + 1) - 1) % MOD
        
        start = 0
        end = N - 1
        
        while start < end:
            if nums[start] + nums[end] > target:
                end -= 1
                continue
                
            ret = (ret + 2 ** (end - start) - 1) % MOD
            start += 1
            
        return ret
        


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums = sorted(nums)
        
        left = 0
        right = len(nums) - 1
        ret = 0
        while left <= right and right < len(nums):
            if nums[left] + nums[right] > target:
                right -= 1
            else:
                ret += 2 ** (right - left)
                ret %= 10**9 + 7
                left += 1
                
        return ret

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        n = len(nums)
        ri = n - 1
        ans = 0
        for li, l in enumerate(nums):
            if l * 2 > target: break
            while nums[ri] + l > target:
                ri -= 1
            ans = (ans + pow(2, ri - li, 1000000007)) % 1000000007
        return ans

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        res = 0
        nums.sort()
        start, end = 0, len(nums) - 1
        
        while (start <= end):
            if (nums[start] + nums[end] <= target):
                res = (res + 2 ** (end - start)) % (10 ** 9 + 7)
                start += 1
            else:
                end -= 1
        
        return res

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        left, right = 0, len(nums)-1
        ans = 0
        mod = 10**9+7
        while left<=right:
            if nums[left] + nums[right] > target:
                right -= 1
            else:
                ans = (ans + 2**(right-left)) % mod
                left += 1
        
        return ans

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums = sorted(nums)
        
        left, right = 0, len(nums)-1
        
        ans = 0
        mod = 10**9+7
        while left<right:
            if nums[left] + nums[right] > target:
                right -= 1
                continue
            else:
                ans = (ans + 2**(right-left)-1) % mod
                left += 1
            
        
        for n in nums:
            if n*2<=target:
                ans += 1
        
        return ans%mod

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        ans=0
        mod=1000000007
        # print(nums)
        st=0
        ed=len(nums)-1
        while(st<ed):
            while(nums[st]+nums[ed]>target):
                ed-=1
            if(st<ed):
                ans+=2**(ed-st)-1
                ans%=mod
            # print(st,ed)
            st+=1
            
            
        for i in range(len(nums)):
            if(2*nums[i]<=target):
                ans+=1
        return ans%mod

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums = sorted(nums)
        ans = i = 0
        while i < len(nums) and nums[i] <= target // 2:
            j = self.help(nums, target-nums[i])
            if j >= i:
                ans += 2**(j-i) % (10**9 + 7)
            i += 1
        return ans % (10**9 + 7)
    
    def help(self, nums, target):
        i, j = 0, len(nums)-1
        while i < j:
            mid = i + (j - i+ 1) // 2
            if nums[mid] <= target:
                i = mid
            else:
                j = mid - 1
        return i
        


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        mod = 10 ** 9 + 7
        count = 0
        left= 0
        right = len(nums) - 1
        
        while left <= right:
            if nums[left] + nums[right] <= target:
                count = (count + pow(2, right - left, mod)) % mod
                left += 1
            else:
                right -= 1
        return count

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        n = len(nums)
        res = 0
        mod = 10 ** 9 + 7

        f = [1] + [0] * (n - 1)
        for i in range(1, n):
            f[i] = f[i - 1] * 2 % mod

        pos = n - 1
        for i, num in enumerate(nums):
            while nums[pos] + num > target and pos >= i:
                pos -= 1
            if pos >= i:
                res += f[pos - i]
            else:
                break
        return res % mod

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        cnt = 0
        mod = 10**9 + 7

        if nums[-1] <= (target // 2):
            return (pow(2, len(nums), mod) - 1)
        
        end = len(nums) - 1
        while end >= 0 and nums[0] + nums[end] > target:
            end -= 1

        print (end)
        for start in range(len(nums)):
            while (start <= end) and (nums[start] + nums[end]) > target:
                end -= 1
            
            if start > end:
                break
            print((start, end))
            cnt += pow(2, (end-start), mod)
            cnt %= mod
        
        
        return cnt
        


class Solution:
    def numSubseq(self, A, target):
        A.sort()
        l, r = 0, len(A) - 1
        res = 0
        mod = 10**9 + 7
        while l <= r:
            if A[l] + A[r] > target:
                r -= 1
            else:
                res += pow(2, r - l, mod)
                l += 1
        return res % mod

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        res = 0
        MOD = 10**9 + 7
        p = 0
        while p < len(nums):
            while p < len(nums) and nums[p] + nums[-1] > target:
                nums.pop()
            if len(nums)-p-1 >= 0:
                res += pow(2, len(nums)-p-1, MOD)
            p += 1
        return res%MOD


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        res = 0
        mod = (10**9+7)
        nums.sort()
        left, right = 0, len(nums)-1
        while left <= right:
            if nums[left] + nums[right] <= target:
                res += pow(2, right - left, mod)
                left += 1
            else:
                right -= 1
        return res % (10**9+7)


class Solution:
    def numSubseq(self, lis: List[int], tar: int) -> int:
        n = len(lis)
        mod = 1000000000 + 7
        lis.sort()
        i=0
        j=n-1
        ans=0
        tmp = pow(2,n,mod) - 1 
        while i<=j:
            if lis[i]+lis[j]<=tar:
                i+=1
            else:
                ans+=pow(2,j-i,mod)
                ans = ans%mod
                j-=1
        print((tmp,ans))
        return (tmp - ans)%mod
                
            


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        mod = 10**9 + 7
        n = len(nums)
        pre = [0] * n
        pre[0] = 1
        res = 0
        for i in range(1, n):
            pre[i] = (pre[i - 1] * 2) % mod
                
        start, end = 0, n - 1
        while start <= end:
            if (nums[start] + nums[end] > target):
                end -= 1
            else:
                res = (res + pre[end - start]) % mod
                start += 1
               
            
            
            
        
        return res % mod


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        res=0
        mod=10**9+7
        left,right=0,len(nums)-1
        for left in range(len(nums)):
            while left<right and nums[left]+nums[right]>target:
                right-=1
            if left<=right and nums[left]+nums[right]<=target:
                print((nums[left],nums[right]))
                res+=pow(2,(right-left),mod)
                res%=mod
                
        return res
                


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        A = nums
        A.sort()
        l, r = 0, len(A) - 1
        res = 0
        mod = 10**9 + 7
        while l <= r:
            if A[l] + A[r] > target:
                r -= 1
            else:
                res += pow(2, r - l, mod)
                l += 1
        return res % mod

class Solution:
    
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        i = 0
        j = len(nums) - 1
        count = 0
        mod = 10**9+7
        while i <= j:
            minv = nums[i]
            maxv = nums[j]
            sumv = minv + maxv 
            if sumv > target:
                j -= 1
            else:
                count = (count + pow(2, j-i, mod)) % mod
                i += 1
        return count

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        
        
        nums.sort()
        l, r = 0, len(nums) - 1
        res = 0
        mod = 10**9 + 7
        while l <= r:
            print((l,r))
            if nums[l] + nums[r] > target:
                r -= 1
            else:
                res += pow(2, r - l, mod)
                l += 1
        return res % mod
            
                
            
            
            
            


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        if not nums:
            return 0
        nums.sort()
        mod = 10**9 + 7
        
        y = len(nums) - 1
        x = 0
        ans = 0
        while x <= y:
            if nums[y] + nums[x] > target:
                y -= 1
            else:
                ans = (ans + pow(2, y-x, mod)) % mod
                x += 1
        return ans

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        total = 0
        MOD = 10**9+7
        lo, hi = 0, len(nums)-1
        
        while lo <= hi:
            if nums[lo] + nums[hi] > target:
                hi -= 1
            else:
                total += pow(2, hi-lo, MOD)
                lo += 1
                
        return total%MOD


class Solution:
    #Version 1: Sliding window
    #Count the mismatch count
    #TC: O(nlogn), SC: O(1)
    '''
    def numSubseq(self, nums: List[int], target: int) -> int:
        M = 10**9 + 7
        mismatch = 0
        nums.sort()
        base = 0
        for k in range(len(nums)):
            if nums[k]*2 > target:
                while base > 0 and nums[base] + nums[k] > target:
                    base -= 1
                while base < k and nums[base] + nums[k] <= target:
                    base += 1
                mismatch += pow(2, k-base, M)
        return (pow(2, len(nums), M) - 1 - mismatch) % M
    '''
    
    def numSubseq(self, nums: List[int], target: int) -> int:
        M = 10**9 + 7
        ans = 0
        nums.sort()
        left = 0
        right = len(nums) - 1
        while left <= right:
            total = nums[left] + nums[right]
            if total <= target:
                ans += pow(2, right-left, M)
            if total > target:
                right -= 1
            else:
                left += 1
        return ans % M


class Solution:        
    def numSubseq(self, A, target):
        A.sort()
        l, r = 0, len(A) - 1
        res = 0
        mod = 10**9 + 7
        while l <= r:
            if A[l] + A[r] > target:
                r -= 1
            else:
                res += pow(2, r - l, mod)
                l += 1
        return res % mod

    
#         self.dfs
#         return res
    
#     def dfs(self, nums, path, res):

#         if max(path) + min(path) <= target:
#             res.append(path)
#             return 
        
        
#         for i in range(nums):
#             self.dfs(nums[i+1:], path+nums[i], res)


class Solution:        
    def numSubseq(self, A, target):
        A.sort()
        l, r = 0, len(A) - 1
        res = 0
        mod = 10**9 + 7
        while l <= r:
            if A[l] + A[r] > target:
                r -= 1
            else:
                res += pow(2, r - l, mod)
                #res += 2**(r-l)
                l += 1
        return res % mod

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        mod = 10 ** 9 + 7
        
        # It is OK to sort the array because the question
        # is essentially asking for the number of subsets,
        # and the order doesn't matter.
        nums.sort()
        i, j = 0, len(nums)-1
        count = 0
        
        # nums[i] is the minimum element,
        # nums[j] is the maximum element,
        # a subset starting with the minimum element
        # contains at least the minimum element.
        # for nums[i+1] to nums[j], it can be included or not.
        # So totally there are 2 ** (j-i) subsets.
        while i <= j:
            while i <= j and nums[i] + nums[j] > target:
                j -= 1
            if i <= j:
                # Compare to (2 ** (j-1)) % mod,
                # using pow function is faster.
                count += pow(2, j-i, mod)
                i += 1
        return count % mod

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        left, right = 0, len(nums) - 1
        ans, mod = 0, 10**9 + 7
        while left <= right:
            if nums[left] + nums[right] > target:
                right -= 1
            else:
                ans += pow(2, right - left, mod)
                #ans %= mod
                left += 1
        return ans % mod

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        mod = 10**9 + 7
        res = 0
        nums.sort()
        l, r = 0, len(nums)-1
        while l <= r:
            if nums[l] + nums[r] > target: r-= 1
            else:
                res += pow(2, r-l, mod)
                l += 1
        return res % mod

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        
        nums.sort()
        l, r = 0, len(nums) - 1
        res = 0
        mod = 10**9 + 7
        while l <= r:
            if nums[l] + nums[r] > target:
                r -= 1
            else:
                res += pow(2, r - l, mod)
                l += 1
        return res % mod

class Solution:
    #Version 1: Sliding window
    #Count the mismatch count
    #TC: O(nlogn), SC: O(1)
    '''
    def numSubseq(self, nums: List[int], target: int) -> int:
        from bisect import bisect_left
        M = 10**9 + 7
        mismatch = 0
        nums.sort()
        base = 0
        for k in range(len(nums)):
            if nums[k]*2 > target:
                # while base > 0 and nums[base] + nums[k] > target:
                #     base -= 1
                # while base < k and nums[base] + nums[k] <= target:
                #     base += 1
                base = bisect_left(nums, target - nums[k]+1)
                mismatch += pow(2, k-base, M)
        return (pow(2, len(nums), M) - 1 - mismatch) % M
    '''
        
    #Version 2: Sliding window
    #Consider the valid count
    #TC: O(nlogn), SC: O(1)
    
    def numSubseq(self, nums: List[int], target: int) -> int:
        from bisect import bisect_left
        M = 10**9 + 7
        pows = [1]*(len(nums)+1)
        for k in range(1, len(pows)):
            pows[k] = (pows[k-1]<<1) % M
        ans = 0
        nums.sort()
        base = 0
        for k in range(len(nums)):
            if nums[k]*2 <= target:
                ans += pows[k]
            else:
                # while base > 0 and nums[base] + nums[k] > target:
                #     base -= 1
                # while base < k and nums[base] + nums[k] <= target:
                #     base += 1
                base = bisect_left(nums, target - nums[k]+1)
                #ans += (pow(2, base, M) - 1) * pow(2, k-base, M)
                ans += (pows[base]-1)*pows[k-base]
            #print(k, base, ans)
        return ans % M
    
    
    #Version 2: Two sum
    #Once the window is valid, we can add the number of subsequences with left or right number
    #TC: O(nlogn), SC: O(1)
    '''
    def numSubseq(self, nums: List[int], target: int) -> int:
        M = 10**9 + 7
        pows = [1]*(len(nums)+1)
        for k in range(1, len(pows)):
            pows[k] = (pows[k-1]<<1) % M
        ans = 0
        nums.sort()
        left = 0
        right = len(nums) - 1
        while left <= right:
            total = nums[left] + nums[right]
            if total > target:
                right -= 1
            else:
                ans = (ans + pows[right-left]) % M
                left += 1
        return ans
    '''

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        n = len(nums)
        nums.sort()
        ans = 0
        l, r = 0, n - 1
        mod = 10**9 + 7
        while l <= r:
            if nums[l] + nums[r] <= target:
                ans += pow(2, r-l , mod)
                l += 1
            else:
                r -= 1
        return ans % mod


import math
import random
import string
from functools import lru_cache
from operator import truediv
from typing import List
import collections
import functools
import heapq
import itertools
import sys
from functools import lru_cache
from typing import List
import numpy as np
import collections
import functools
import heapq
import itertools
import sys
from functools import lru_cache
from typing import List

'''
Input: nums = [3,5,6,7], target = 9
Output: 4
Explanation: There are 4 subsequences that satisfy the condition.
[3] -> Min value + max value <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)

普通思路：排序。分别计算各个区间
3 -> 1
3 5 -> 2^0 在或不在
3 5 6 -> 2^1
3 5 6 7 -> 2^2

加强，与其每次计算，不如到最后一个才计算，因为：
1 + 2^0 + 2^1 + 2^2 = 2^3

可以用二分加速寻找。
'''


class Solution:
    def numSubseqNormal(self, nums: List[int], target: int) -> int:
        nums = sorted(nums)
        n = len(nums)
        count = 0
        mod = 10 ** 9 + 7
        for i in range(n):
            for j in range(i, n):
                if (nums[i] + nums[j]) <= target:
                    if i == j:
                        count += 1
                    else:
                        count += pow(2, j - i - 1)
                    count %= mod
        return count

    # 加强
    def numSubseq1(self, nums: List[int], target: int) -> int:
        nums = sorted(nums)
        n = len(nums)
        count = 0
        mod = 10 ** 9 + 7
        for i in range(n):
            j = i
            while j < n and (nums[i] + nums[j]) <= target:
                j += 1
            if i == j:
                if (nums[i] + nums[j]) <= target:
                    count += 1
            elif (nums[i] + nums[j - 1]) <= target:  # 防止第一个数就超过
                count += pow(2, j - i - 1) % mod
        return count % mod

    def findLast(self, nums, start, end, target):
        first = nums[start]
        while start <= end:
            mid = int((start + end) / 2)
            second = nums[mid]
            if first + second > target:
                end = mid - 1
            elif first + second < target:
                start = start + 1
            elif first + second == target:
                start = start + 1
        return start

    def numSubseq12(self, nums: List[int], target: int) -> int:
        nums = sorted(nums)
        n = len(nums)
        count = 0
        mod = 10 ** 9 + 7
        pow_map = [1 for _ in range(n)]
        for i in range(1, n):
            pow_map[i] = (2 * pow_map[i - 1]) % mod

        for i in range(n):
            if nums[i] > target:
                    break
            j = self.findLast(nums, i, n - 1, target)
            if i == j:
                if (nums[i] + nums[j]) <= target:
                    count += 1
            elif (nums[i] + nums[j - 1]) <= target:  # 防止第一个数就超过
                count += pow_map[j - i - 1]
        return count % mod
    
    
    def numSubseq(self, A, target):
        A.sort()
        l, r = 0, len(A) - 1
        res = 0
        mod = 10**9 + 7
        while l <= r:
            if A[l] + A[r] > target:
                r -= 1
            else:
                res += pow(2, r - l, mod)
                l += 1
        return res % mod

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1
        output, nums = 0, sorted(nums)
        while l <= r:
            if nums[l] + nums[r] <= target:
                output += pow(2, r - l, 10 ** 9 + 7)
                l += 1
            else:
                r -= 1
        return output % (10 ** 9 + 7)
    
    # def numSubseq(self, A, target):
    #     A.sort()
    #     l, r = 0, len(A) - 1
    #     res = 0
    #     mod = 10**9 + 7
    #     while l <= r:
    #         if A[l] + A[r] > target:
    #             r -= 1
    #         else:
    #             res += pow(2, r - l, mod)
    #             l += 1
    #     return res % mod


class Solution:
    #Version 1: Sliding window
    #Count the mismatch count
    #TC: O(nlogn), SC: O(1)
    '''
    def numSubseq(self, nums: List[int], target: int) -> int:
        M = 10**9 + 7
        mismatch = 0
        nums.sort()
        base = 0
        for k in range(len(nums)):
            if nums[k]*2 > target:
                while base > 0 and nums[base] + nums[k] > target:
                    base -= 1
                while base < k and nums[base] + nums[k] <= target:
                    base += 1
                mismatch += pow(2, k-base, M)
        return (pow(2, len(nums), M) - 1 - mismatch) % M
    '''
    
    #Version 2: Two sum
    #
    def numSubseq(self, nums: List[int], target: int) -> int:
        M = 10**9 + 7
        pows = [1]*(len(nums)+1)
        for k in range(1, len(pows)):
            pows[k] = (pows[k-1]*2) % M
        ans = 0
        nums.sort()
        left = 0
        right = len(nums) - 1
        while left <= right:
            total = nums[left] + nums[right]
            if total <= target:
                ans += pows[right-left]
            if total > target:
                right -= 1
            else:
                left += 1
        return ans % M


from itertools import combinations

class Solution:
    def numSubseq(self, A, target) -> int:
        MOD = 10 ** 9 + 7
        N = len(A)
        A.sort()
        
        ans = 0
        j = N - 1
        for i in range(N):
            while i < j and A[i] + A[j] > target:
                j -= 1
                
            if A[i] + A[j] <= target:
                ans += pow(2, j - i, MOD)
                ans %= MOD
                
        return ans


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        s , e = 0 , len(nums) -1
        mod = 10**9 + 7
        result = 0
        while s <= e:
            if nums[s] + nums[e] <= target:                
                result += pow(2,e- s, mod)
                s += 1
            else:
                e -=1            
        return result % mod

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        count = 0
        j = len(nums) - 1
        mod = 10**9 + 7
        for i in range(len(nums)):
            while i <= j and nums[i] + nums[j] > target:
                j -= 1
            
            if i <= j and nums[i] + nums[j] <= target:
                count += pow(2, j-i, mod)
                count = count % mod
                
        return count

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        i, j = 0, len(nums) - 1
        ans = 0
        mod = 10**9 + 7
        while i <= j:
            if nums[i] + nums[j] > target:
                j -= 1
            else:
                ans += self.fast_pow_mod(2, j - i, mod)
                i += 1
        return ans % mod
    
    def fast_pow_mod(self, a, b, m):
        ans = 1
        while b != 0:
            if (b & 1) == 1:
                ans = (ans * a) % m
            b >>= 1
            a = (a * a) % m
        return ans



import math
class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        check = {0:1}
        nums.sort()
        
        n = len(nums)
        right = n-1
        cur =  1
        for i in range(1, n+1):
            cur = (2*cur) % 1000000007
            check[i] = cur
        result = 0
        for i in range(n):
            while right >= i and nums[i] + nums[right] > target:
                right -= 1
            if right < i:
                break
            extra = right - i
            if nums[i] + nums[right] <= target:
                result += check[extra] % (1000000007)    
        return result % (1000000007)


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        MOD = 10 ** 9 + 7
        nums.sort()
        right = len(nums) - 1
        count = 0
        pow2 = [1 for _ in range(len(nums))]
        for i in range(len(pow2)):
            if i>0:
                pow2[i] = (pow2[i-1] * 2) % MOD
        for i in range(len(nums)):
            while right>=i and nums[i] + nums[right] > target:
                right -= 1
            if right < i:
                break
            else:
                count += pow2[right - i]
            count %= MOD
        return count % MOD


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        mod = 10 ** 9 + 7
        nums.sort()
        result = 0
        i, j = 0, len(nums) - 1
        while i <= j:
            cur_sum = nums[i] + nums[j]
            if cur_sum <= target:
                result += pow(2, j - i, mod)
                i += 1
            else:
                j -= 1
        return result % mod

class Solution:
    def numSubseq(self, A: List[int], target: int) -> int:
        A.sort()
        l, r = 0, len(A) - 1
        res = 0
        mod = 10**9 + 7
        while l <= r:
            if A[l] + A[r] > target:
                r -= 1
            else:
                res += pow(2, r - l, mod)
                l += 1
        return res % mod

class Solution:
     def numSubseq(self, A, target):
        A.sort()
        l, r = 0, len(A) - 1
        res = 0
        mod = 10**9 + 7
        while l <= r:
            if A[l] + A[r] > target:
                r -= 1
            else:
                res += pow(2, r - l, mod)
                l += 1
        return res % mod


from bisect import bisect_right
class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        arr=[]
        n=len(nums)
        m=10**9+7
        nums.sort()
        ans=0
        dp=[0]*n
        if 2*nums[0]<=target:
            dp[0]=1
        for i in range(1,n):
            if 2*nums[i]<=target:
                dp[i]=(2*dp[i-1]%m+1%m)%m
                
            elif nums[i]<target:
                index=bisect_right(nums,target-nums[i])
                
                dp[i]=(dp[i-1]%m+dp[index-1]%m+dp[index-1]%m*(pow(2,i-index,m)-1))%m
                    
            else:
                dp[i]=dp[i-1]
        print(dp)
                    
        return dp[n-1]%m
        
                
        
            
                
            
                
        
        


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        n = len(nums)
        l,r = 0, n-1
        counts = 0
        res = 0
        
        while l<=r:
            while l<=r and nums[r]+nums[l]>target:
                r -= 1
            if l<=r:
                res += pow(2, (r-l), 10**9+7)
                res %= 10**9 + 7
                l += 1
            
        return res 


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        i = 0
        j = len(nums) - 1
        mod = 10 ** 9 + 7
        
        count = 0
        while i <= j:
            if nums[i] + nums[j] > target:
                j -= 1
            else:
                count += pow(2, j - i, mod)
                i += 1
        
        return count % mod

class Solution:
    #Version 1: Sliding window
    #Count the mismatch count
    #TC: O(nlogn), SC: O(1)
    '''
    def numSubseq(self, nums: List[int], target: int) -> int:
        from bisect import bisect_left
        M = 10**9 + 7
        mismatch = 0
        nums.sort()
        base = 0
        for k in range(len(nums)):
            if nums[k]*2 > target:
                # while base > 0 and nums[base] + nums[k] > target:
                #     base -= 1
                # while base < k and nums[base] + nums[k] <= target:
                #     base += 1
                base = bisect_left(nums, target - nums[k]+1)
                mismatch += pow(2, k-base, M)
        return (pow(2, len(nums), M) - 1 - mismatch) % M
    '''
        
    #Version 2: Sliding window
    #Consider the valid count
    #TC: O(nlogn), SC: O(1)
    '''   
    def numSubseq(self, nums: List[int], target: int) -> int:
        from bisect import bisect_left
        M = 10**9 + 7
        pows = [1]*(len(nums)+1)
        for k in range(1, len(pows)):
            pows[k] = (pows[k-1]<<1) % M
        ans = 0
        nums.sort()
        base = 0
        for k in range(len(nums)):
            if nums[k]*2 <= target:
                ans += pows[k]
            else:
                # while base > 0 and nums[base] + nums[k] > target:
                #     base -= 1
                # while base < k and nums[base] + nums[k] <= target:
                #     base += 1
                base = bisect_left(nums, target - nums[k]+1)
                ans += (pows[base]-1)*pows[k-base]
            #print(k, base, ans)
        return ans % M
    '''
    
    #Version 3: Two sum
    #Once the window is valid, we can add the number of subsequences with left or right number
    #TC: O(nlogn), SC: O(1)
    def numSubseq(self, nums: List[int], target: int) -> int:
        M = 10**9 + 7
        pows = [1]*(len(nums)+1)
        for k in range(1, len(pows)):
            pows[k] = (pows[k-1]<<1) % M
        ans = 0
        nums.sort()
        left = 0
        right = len(nums) - 1
        while left <= right:
            total = nums[left] + nums[right]
            if total > target:
                right -= 1
            else:
                ans = (ans + pows[right-left]) % M
                left += 1
        return ans


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        
        nums.sort()
        
        l , r = 0 ,len(nums)-1
        mod = 10**9+7
        ans = 0
        
        while l <= r:
            if nums[l] + nums[r] > target:
                r -= 1
            else :
                ans += pow(2,r-l , mod)
                l += 1
        
        return ans % mod

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        
        mod = 10**9 + 7
        
        nums.sort()
        l = 0
        r = len(nums) - 1
        ans = 0

        while l <= r:
            if nums[l] + nums[r] <= target:
                ans += pow(2, r - l, mod) 
                l += 1
            else:
                r -= 1
        return ans % mod    

        
        
        


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        '''
         将数组排序，找符合条件的子序列的最小值与最大值
         从每一项开始，寻找符合条件的最大值位置
            In subarray nums[i~j]:
            min = nums[i], max = nums[j]
            nums[i] + nums[j] <= target
            {nums[i], (j - i - 1 + 1 values)}
            Any subset of the right part gives a valid subsequence 
            in the original array. And There are 2^(j - i) ones.
        '''
        n=len(nums)
        nums.sort()
        p=[1]*(n+1)
        for i in range(1,n+1):
            p[i]=(p[i-1]<<1)%(10**9+7)
        res=0
        j=n-1
        for i in range(j+1):
            while i<=j and nums[i]+nums[j]>target:
                j-=1
            if i>j:
                continue
            res=(res+p[j-i])%(10**9+7)
        return res


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        M = 10**9 + 7
        mismatch = 0
        nums.sort()
        base = 0
        for k in range(len(nums)):
            if nums[k]*2 > target:
                while base > 0 and nums[base] + nums[k] > target:
                    base -= 1
                while base < k and nums[base] + nums[k] <= target:
                    base += 1
                mismatch += pow(2, k-base, M)
        return (pow(2, len(nums), M) - 1 - mismatch) % M

import math
import random
import string
from functools import lru_cache
from operator import truediv
from typing import List
import collections
import functools
import heapq
import itertools
import sys
from functools import lru_cache
from typing import List
import numpy as np
import collections
import functools
import heapq
import itertools
import sys
from functools import lru_cache
from typing import List

'''
Input: nums = [3,5,6,7], target = 9
Output: 4
Explanation: There are 4 subsequences that satisfy the condition.
[3] -> Min value + max value <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)

普通思路：排序。分别计算各个区间
3 -> 1
3 5 -> 2^0 在或不在
3 5 6 -> 2^1
3 5 6 7 -> 2^2

加强，与其每次计算，不如到最后一个才计算，因为：
1 + 2^0 + 2^1 + 2^2 = 2^3

可以用二分加速寻找。

终极优化：对比二分或者for循环找最后一个，实际上还是做了大量重复的比较。

根据+法的特点进行双端优化，大于target则右侧减一，小于target则左侧加一。
'''


class Solution:
    def numSubseqNormal(self, nums: List[int], target: int) -> int:
        nums = sorted(nums)
        n = len(nums)
        count = 0
        mod = 10 ** 9 + 7
        for i in range(n):
            for j in range(i, n):
                if (nums[i] + nums[j]) <= target:
                    if i == j:
                        count += 1
                    else:
                        count += pow(2, j - i - 1)
                    count %= mod
        return count

    # 加强
    def numSubseq1(self, nums: List[int], target: int) -> int:
        nums = sorted(nums)
        n = len(nums)
        count = 0
        mod = 10 ** 9 + 7
        for i in range(n):
            j = i
            while j < n and (nums[i] + nums[j]) <= target:
                j += 1
            if i == j:
                if (nums[i] + nums[j]) <= target:
                    count += 1
            elif (nums[i] + nums[j - 1]) <= target:  # 防止第一个数就超过
                count += pow(2, j - i - 1) % mod
        return count % mod

    def findLast(self, nums, start, end, target):
        first = nums[start]
        while start <= end:
            mid = int((start + end) / 2)
            second = nums[mid]
            if first + second > target:
                end = mid - 1
            elif first + second < target:
                start = start + 1
            elif first + second == target:
                start = start + 1
        return start

    def numSubseq12(self, nums: List[int], target: int) -> int:
        nums = sorted(nums)
        n = len(nums)
        count = 0
        mod = 10 ** 9 + 7
        pow_map = [1 for _ in range(n)]
        for i in range(1, n):
            pow_map[i] = (2 * pow_map[i - 1]) % mod

        for i in range(n):
            if nums[i] > target:
                    break
            j = self.findLast(nums, i, n - 1, target)
            if i == j:
                if (nums[i] + nums[j]) <= target:
                    count += 1
            elif (nums[i] + nums[j - 1]) <= target:  # 防止第一个数就超过
                count += pow_map[j - i - 1]
        return count % mod

    # 双端优化
    def numSubseq(self, A, target):
        A.sort()
        l, r = 0, len(A) - 1
        res = 0
        mod = 10**9 + 7
        while l <= r:
            if A[l] + A[r] > target:
                r -= 1
            else:
                res += pow(2, r - l, mod)
                l += 1
        return res % mod

class Solution:
     def numSubseq(self, A, target):
        A.sort()
        l, r = 0, len(A) - 1
        res = 0
        mod = 10**9 + 7
        while l <= r:
            if A[l] + A[r] > target:
                r -= 1
            else:
                res += pow(2, r - l, mod)%mod
                l += 1
        return res % mod

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        MOD = 10 ** 9 + 7
        
        nums.sort()
        cnt = 0
        lo = 0
        hi = len(nums) - 1
        while lo <= hi:
            if nums[lo] + nums[hi] > target:
                hi -= 1
            else:
                cnt += pow(2, hi - lo, MOD)
                lo += 1
        return cnt % MOD

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        if nums is None and len(nums) == 0:
            return 0 
        
        nums.sort()
        mod = 10**9 + 7 
        ans = 0
        left, right = 0, len(nums) - 1 
        
        
        while left <= right:
            if nums[left] + nums[right] > target:
                right -= 1 
            else:
                ans += pow(2, right-left, mod)
                left += 1 
        
        return ans % mod

class Solution:
    #Version 1: Sliding window
    #Count the mismatch count
    #TC: O(nlogn), SC: O(1)
    '''
    def numSubseq(self, nums: List[int], target: int) -> int:
        from bisect import bisect_left
        M = 10**9 + 7
        mismatch = 0
        nums.sort()
        base = 0
        for k in range(len(nums)):
            if nums[k]*2 > target:
                # while base > 0 and nums[base] + nums[k] > target:
                #     base -= 1
                # while base < k and nums[base] + nums[k] <= target:
                #     base += 1
                base = bisect_left(nums, target - nums[k]+1)
                mismatch += pow(2, k-base, M)
        return (pow(2, len(nums), M) - 1 - mismatch) % M
    '''
        
    #Version 2: Sliding window
    #Consider the valid count
    #TC: O(nlogn), SC: O(1)
    '''
    def numSubseq(self, nums: List[int], target: int) -> int:
        from bisect import bisect_left
        M = 10**9 + 7
        pows = [1]*(len(nums)+1)
        for k in range(1, len(pows)):
            pows[k] = (pows[k-1]<<1) % M
        ans = 0
        nums.sort()
        base = 0
        for k in range(len(nums)):
            if nums[k]*2 <= target:
                ans += pow(2, k, M)
            else:
                # while base > 0 and nums[base] + nums[k] > target:
                #     base -= 1
                # while base < k and nums[base] + nums[k] <= target:
                #     base += 1
                base = bisect_left(nums, target - nums[k]+1)
                ans += (pow(2, base, M) - 1) * pow(2, k-base, M)
            #print(k, base, ans)
        return ans % M
    '''
    
    #Version 2: Two sum
    #Once the window is valid, we can add the number of subsequences with left or right number
    #TC: O(nlogn), SC: O(1)
    def numSubseq(self, nums: List[int], target: int) -> int:
        M = 10**9 + 7
        pows = [1]*(len(nums)+1)
        for k in range(1, len(pows)):
            pows[k] = (pows[k-1]<<1) % M
        ans = 0
        nums.sort()
        left = 0
        right = len(nums) - 1
        while left <= right:
            total = nums[left] + nums[right]
            if total > target:
                right -= 1
            else:
                ans = (ans + pows[right-left]) % M
                left += 1
        return ans


class Solution:
     def numSubseq(self, A, target):
        A.sort()
        l, r = 0, len(A) - 1
        res = 0
        mod = 10**9 + 7
        while l <= r:
            if A[l] + A[r] > target:
                r -= 1
            else:
                res += pow(2, r - l, mod)
                l += 1
        return res % mod

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        le = len(nums)
        res = 0
        mod=10**9+7
        j = le-1
        for i in range(le):
            while j>=i and nums[i]+nums[j]>target:
                j-=1
            if j<i:
                break
            res += pow(2,j-i,mod)
            res%=mod
        return res

class Solution:
    #Version 1: Sliding window
    #Count the mismatch count
    #TC: O(nlogn), SC: O(1)
    
    def numSubseq(self, nums: List[int], target: int) -> int:
        from bisect import bisect_left
        M = 10**9 + 7
        mismatch = 0
        nums.sort()
        base = 0
        for k in range(len(nums)):
            if nums[k]*2 > target:
                # while base > 0 and nums[base] + nums[k] > target:
                #     base -= 1
                # while base < k and nums[base] + nums[k] <= target:
                #     base += 1
                base = bisect_left(nums, target - nums[k]+1)
                mismatch += pow(2, k-base, M)
        return (pow(2, len(nums), M) - 1 - mismatch) % M

    
    #Version 2: Two sum
    #Once the window is valid, we can add the number of subsequences with left or right number
    #TC: O(nlogn), SC: O(1)
    '''
    def numSubseq(self, nums: List[int], target: int) -> int:
        M = 10**9 + 7
        pows = [1]*(len(nums)+1)
        for k in range(1, len(pows)):
            pows[k] = (pows[k-1]<<1) % M
        ans = 0
        nums.sort()
        left = 0
        right = len(nums) - 1
        while left <= right:
            total = nums[left] + nums[right]
            if total > target:
                right -= 1
            else:
                ans = (ans + pows[right-left]) % M
                left += 1
        return ans
    '''
    
    #Version 3: Sliding window
    #Consider the valid count
    #TC: O(nlogn), SC: O(1)
    '''
    def numSubseq(self, nums: List[int], target: int) -> int:
        from bisect import bisect_left
        M = 10**9 + 7
        pows = [1]*(len(nums)+1)
        for k in range(1, len(pows)):
            pows[k] = (pows[k-1]<<1) % M
        ans = 0
        nums.sort()
        base = 0
        for k in range(len(nums)):
            if nums[k]*2 <= target:
                ans += pow(2, k, M)
            else:
                # while base > 0 and nums[base] + nums[k] > target:
                #     base -= 1
                # while base < k and nums[base] + nums[k] <= target:
                #     base += 1
                base = bisect_left(nums, target - nums[k]+1)
                ans += (pow(2, base, M) - 1) * pow(2, k-base, M)
            #print(k, base, ans)
        return ans % M
    '''