<p>You are given an array of integers <code>nums</code> and an integer <code>target</code>.</p>

<p>Return <em>the number of <strong>non-empty</strong> subsequences of </em><code>nums</code><em> such that the sum of the minimum and maximum element on it is less or equal to </em><code>target</code>. Since the answer may be too large, return it <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

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

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [3,3,6,8], target = 10
<strong>Output:</strong> 6
<strong>Explanation:</strong> There are 6 subsequences that satisfy the condition. (nums can have repeated numbers).
[3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [2,3,3,4,6,7], target = 12
<strong>Output:</strong> 61
<strong>Explanation:</strong> There are 63 non-empty subsequences, two of them do not satisfy the condition ([6,7], [7]).
Number of valid subsequences (63 - 2 = 61).
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>6</sup></code></li>
	<li><code>1 &lt;= target &lt;= 10<sup>6</sup></code></li>
</ul>

class Solution {
public:
    const int mod = 1e9 + 7; 
    static vector<long long> pow2s;
    
    Solution() {
        if(pow2s.empty()) {
            ios::sync_with_stdio(0);
            cin.tie(0);
            pow2s.resize(100010);
            pow2s[0] = 1; 
            for(int i = 1;i<pow2s.size();i++) {
                pow2s[i] = (pow2s[i-1] << 1) % mod; 
            }
        }
    }
    
    int numSubseq(vector<int>& nums, int target) {
        sort(nums.begin(),nums.end());
        pow2s[0] = 1; 
        for(int i = 1;i<nums.size();i++) {
            pow2s[i] = (pow2s[i-1] << 1) % mod; 
        }
        stack<int> s; 
        long long ret = 0; 
        for(int i = 0;i<nums.size();i++) {
            while(s.size() && nums[i] + nums[s.top()] > target) {
                s.pop(); 
            }
            if(s.size()) {
                long long total = pow2s[i] - 1;
                long long not_able = pow2s[i-s.top()-1] - 1; 
                ret += total - not_able + mod; 
                ret %= mod; 
            } 
            s.push(i);
            if(nums[i] + nums[i] <= target) {
                ret += 1; 
            }
        }
        return ret % mod; 
    }
};

vector<long long> Solution:: pow2s; 
54300