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

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

def _disabled_input(*args, **kwargs):
    raise RuntimeError("input() is disabled in callable mode")
builtins.input = _disabled_input

ns = {"__name__": "__judge__"}  # prevent if __name__ == "__main__" blocks
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = "import math\nimport random\nimport string\nfrom functools import lru_cache\nfrom operator import truediv\nfrom typing import List\nimport collections\nimport functools\nimport heapq\nimport itertools\nimport sys\nfrom functools import lru_cache\nfrom typing import List\nimport numpy as np\nimport collections\nimport functools\nimport heapq\nimport itertools\nimport sys\nfrom functools import lru_cache\nfrom typing import List\n\n'''\nInput: nums = [3,5,6,7], target = 9\nOutput: 4\nExplanation: There are 4 subsequences that satisfy the condition.\n[3] -> Min value + max value <= target (3 + 3 <= 9)\n[3,5] -> (3 + 5 <= 9)\n[3,5,6] -> (3 + 6 <= 9)\n[3,6] -> (3 + 6 <= 9)\n\n普通思路：排序。分别计算各个区间\n3 -> 1\n3 5 -> 2^0 在或不在\n3 5 6 -> 2^1\n3 5 6 7 -> 2^2\n\n加强，与其每次计算，不如到最后一个才计算，因为：\n1 + 2^0 + 2^1 + 2^2 = 2^3\n\n可以用二分加速寻找。\n\n终极优化：对比二分或者for循环找最后一个，实际上还是做了大量重复的比较。\n\n根据+法的特点进行双端优化，大于target则右侧减一，小于target则左侧加一。\n'''\n\n\nclass Solution:\n    def numSubseqNormal(self, nums: List[int], target: int) -> int:\n        nums = sorted(nums)\n        n = len(nums)\n        count = 0\n        mod = 10 ** 9 + 7\n        for i in range(n):\n            for j in range(i, n):\n                if (nums[i] + nums[j]) <= target:\n                    if i == j:\n                        count += 1\n                    else:\n                        count += pow(2, j - i - 1)\n                    count %= mod\n        return count\n\n    # 加强\n    def numSubseq1(self, nums: List[int], target: int) -> int:\n        nums = sorted(nums)\n        n = len(nums)\n        count = 0\n        mod = 10 ** 9 + 7\n        for i in range(n):\n            j = i\n            while j < n and (nums[i] + nums[j]) <= target:\n                j += 1\n            if i == j:\n                if (nums[i] + nums[j]) <= target:\n                    count += 1\n            elif (nums[i] + nums[j - 1]) <= target:  # 防止第一个数就超过\n                count += pow(2, j - i - 1) % mod\n        return count % mod\n\n    def findLast(self, nums, start, end, target):\n        first = nums[start]\n        while start <= end:\n            mid = int((start + end) / 2)\n            second = nums[mid]\n            if first + second > target:\n                end = mid - 1\n            elif first + second < target:\n                start = start + 1\n            elif first + second == target:\n                start = start + 1\n        return start\n\n    def numSubseq12(self, nums: List[int], target: int) -> int:\n        nums = sorted(nums)\n        n = len(nums)\n        count = 0\n        mod = 10 ** 9 + 7\n        pow_map = [1 for _ in range(n)]\n        for i in range(1, n):\n            pow_map[i] = (2 * pow_map[i - 1]) % mod\n\n        for i in range(n):\n            if nums[i] > target:\n                    break\n            j = self.findLast(nums, i, n - 1, target)\n            if i == j:\n                if (nums[i] + nums[j]) <= target:\n                    count += 1\n            elif (nums[i] + nums[j - 1]) <= target:  # 防止第一个数就超过\n                count += pow_map[j - i - 1]\n        return count % mod\n\n    # 双端优化\n    def numSubseq(self, A, target):\n        A.sort()\n        l, r = 0, len(A) - 1\n        res = 0\n        mod = 10**9 + 7\n        while l <= r:\n            if A[l] + A[r] > target:\n                r -= 1\n            else:\n                res += pow(2, r - l, mod)\n                l += 1\n        return res % mod"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

_target = None
_fn_name = 'numSubseq'
if _fn_name:
    if "Solution" in ns:
        try:
            _obj = ns["Solution"]()
            if hasattr(_obj, _fn_name):
                _target = getattr(_obj, _fn_name)
        except Exception:
            _target = None
    if _target is None and _fn_name in ns and callable(ns[_fn_name]):
        _target = ns[_fn_name]
# Fallback: if there's exactly one user-defined function, use it
if _target is None:
    _cands = [v for k, v in ns.items() if callable(v) and getattr(v, "__module__", "") in ("__judge__", "__main__")]
    _user_funcs = [c for c in _cands if getattr(c, "__name__", "").startswith("_") is False]
    if len(_user_funcs) == 1:
        _target = _user_funcs[0]
if _target is None:
    raise RuntimeError(f"Could not resolve callable '{_fn_name}'")

_raw = sys.stdin.read().strip()
if _raw:
    _parsed = json.loads(_raw)
    if isinstance(_parsed, dict):
        _kwargs = _parsed.get("kwargs", {})
        _args = _parsed.get("args", [])
    else:
        _args, _kwargs = _parsed, {}
else:
    _args, _kwargs = [], {}
if not isinstance(_args, (list, tuple)):
    _args = [_args]
_res = _target(*_args, **_kwargs)
try:
    sys.stdout.write(repr(_res) + "\n")
except Exception:
    pass

```

Measured memory_bytes: 5494