Optimized solution using Two Pointers with Binary Exponentiation | Solution explained in detail.
\n\n# Approach\nThe given problem requires counting the number of non-empty subsequences of an array of integers nums such that the sum of the minimum and maxim
\n\n# Approach\nThe given problem requires counting the number of non-empty subsequences of an array of integers nums such that the sum of the minimum and maximum element on it is less than or equal to a given integer target. Since the answer may be large, the final result must be returned modulo 10^9 + 7.\n\nThe solution starts by sorting the input array in non-decreasing order, allowing us to easily compare the minimum and maximum elements of any subsequence.\n\nNext, two pointers, left and right, are initialized at the beginning and the end of the sorted array, respectively. The idea is to consider all possible subsequences of nums by varying the left and right endpoints, while counting only those that satisfy the given condition. Specifically, for any pair of indices (left, right) such that nums[left] + nums[right] \u2264 target, we add 2^(right-left) to the answer ans to count the number of subsequences that can be formed between these indices.\n\nThe factor of 2^(right-left) corresponds to the number of ways to choose any subset of elements between left and right, i.e., the number of non-empty subsequences. The running sum of this quantity is maintained in ans. Whenever the sum nums[left] + nums[right] is greater than target, we decrement right, since the minimum and maximum elements in any valid subsequence must add up to less than or equal to target. If nums[left] + nums[right] is less than or equal to target, we increment left and add 2^(right-left) to the answer.\n\nFinally, the function returns the value of ans modulo 10^9 + 7 as required.\n\n# Complexity\n- Time complexity:\nSorting the array takes O(nlogn) time, where n is the length of the input array. The while loop takes O(n) time, since each pointer moves at most n times. The time complexity of the power function is O(log mod) since it uses the binary exponentiation algorithm. Therefore, the overall time complexity is O(nlogn).\n\n- Space complexity:\nThe solution uses constant space, except for the space used to store the sorted array, which takes O(n) space. Therefore, the space complexity of this solution is O(n).\n\n# Code\n```\nclass Solution {\npublic:\n    int numSubseq(vector<int>& nums, int target) {\n        const int MOD = 1e9 + 7;\n        int n = nums.size();\n        sort(nums.begin(), nums.end());\n        int left = 0, right = n - 1;\n        long long ans = 0;\n        while (left <= right) {\n            if (nums[left] + nums[right] > target) {\n                right--;\n            } else {\n                ans = (ans + power(2, right - left, MOD)) % MOD;\n                left++;\n            }\n        }\n        return ans;\n    }\n    \n    int power(int base, int exp, int mod) {\n        long long res = 1;\n        while (exp > 0) {\n            if (exp % 2 == 1) {\n                res = (res * (long long)base) % mod;\n            }\n            base = ((long long)base * base) % mod;\n            exp /= 2;\n        }\n        return (int)res;\n    }\n\n};\n\n```
['Array', 'Two Pointers', 'Binary Search', 'C++', 'Java']