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

Source: leetcode | Difficulty: MEDIUM
Tags: Data structures

Sorting

Amortized analysis

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]
			left += 1
		return res % self.MODS


class Solution:

	def numSubseq(self, nums: List[int], target: int) -> int:
		nums = sorted(nums)
		mod = int(1000000000.0 + 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()
		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:
		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


class Solution:

	def getCombination(self, start, endPos):
		mod = 10 ** 9 + 7
		count = pow(2, endPos - start)
		return count % mod

	def findPos(self, nums, target):
		start = 0
		end = len(nums) - 1
		while start <= end:
			medium = start + (end - start) // 2
			sumv = nums[0] + nums[medium]
			if sumv > target:
				end = medium - 1
			elif sumv == target:
				if medium == len(nums) - 1 or nums[medium + 1] != nums[medium]:
					return medium
				else:
					start = medium + 1
			elif medium == len(nums) - 1 or nums[medium + 1] + nums[0] > target:
				return medium
			else:
				start = medium + 1
		return end

	def numSubseq2(self, nums: List[int], target: int) -> int:
		mod = 10 ** 9 + 7
		nums.sort()
		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]
		return c % 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:
		(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()
		n = len(nums)
		res = 0
		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, 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
		while left <= right:
			while left <= right and nums[left] + nums[right] > target:
				right -= 1
			count += dp[right - left + 1]
			while left <= right and nums[left] + nums[right] <= target:
				left += 1
			count -= dp[right - left + 1]
		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:
		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:
		MOD = int(1000000000.0 + 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()
		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)
		for idx in range(1, len(D)):
			D[idx] = D[idx - 1] * 2
		n = len(nums) - 1
		for (idx, i) in enumerate(nums):
			if i > target - i:
				break
			else:
				best = bisect(target - i, idx, n)
				n = best
				cnt += D[best - idx]
		return cnt % N


class Solution:

	def __init__(self):
		mod = 1000000000.0 + 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 = 1000000000.0 + 7
		nums = sorted(nums)
		sind = 0
		eind = len(nums) - 1
		ans = 0
		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:

	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)
		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 = 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, 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
				l += 1
		return res


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()
		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:
		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:
		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)
		return ans % M


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
		res = (res + sum((2 * n <= target for n in nums))) % MOD
		return res


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:
		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
		(l, r) = (0, n - 1)
		res = 0
		while 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
			elif mid == h or arr[mid + 1] > x:
				return mid
			else:
				l = mid + 1

	def numSubseq(self, nums: List[int], target: int) -> int:
		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:
		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:
		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)
				l += 1
			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)
		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
					break
				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:]
		output = 0
		start = 0
		end = len(hulu) - 1
		while start < len(hulu):
			while end >= start:
				if hulu[start] + hulu[end] <= target:
					output += (2 ** dic[hulu[start]] - 1) * 2 ** (dahulu[end] - dahulu[start])
					break
				else:
					end -= 1
			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(1000000000.0 + 7)


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()
		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()
		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:
		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
		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


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)


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:

	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, 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)
		return cnt % (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:
		nums.sort()
		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
			count += 2 ** (j - i)
		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 = 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:
		(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:
		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()
		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()
		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.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:
			while i < j and nums[i] + nums[j] > target:
				j -= 1
			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:
		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)


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
		return 2 ** (start - ind)

	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)
				result += res
			else:
				break
		return result % (10 ** 9 + 7)


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()
		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
			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):
			if nums[lft] * 2 > target:
				break
			(lo, hi) = (lft, N - 1)
			while lo + 1 < hi:
				m = (lo + hi) // 2
				if nums[lft] + nums[m] <= target:
					lo = m
				else:
					hi = m
			if nums[lft] + nums[hi] > target:
				ans += 2 ** (lo - lft)
			else:
				ans += 2 ** (hi - lft)
		return ans % (10 ** 9 + 7)


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


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()
		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:
		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, 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 = 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, 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:

		def find_right(nums, j, target):
			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 = (res + pow(2, right - left)) % MOD
				left += 1
			else:
				right -= 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()
		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, 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, 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()
		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:
		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


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.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:
		nums.sort()
		ans = 0
		mod = 1000000007
		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
			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.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, 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, 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:
		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:
		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


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

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:
		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()
		(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


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:
		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