<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 {
    const int MOD = 1e9+7;
    // vector
    // int calcPowerOfTwo(int n){
    //     int i=0;
    //     for(i=0; i<=n; i++){
    //         ans
    //     }
    // }
public:
    int numSubseq(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());


        int i=0, n=nums.size(),ans=0,j=n-1,powMod=1;
        vector<int> calcPow={1};
        for(i=0; i<n; i++){
            powMod = (powMod*2)%MOD;
            calcPow.push_back(powMod);
        }

        
        for(i=0; i<=j; i++){
            // if(2*nums[i]<=target)ans++;
            while(i<=j&&nums[i]+nums[j]>target){
                j--;
            }
            if(i<=j){
                // cout<<j-i<<endl;
                ans=(ans+calcPow[j-i])%MOD;
                // cout<<i<<" "<<ans<<endl;
            }
        }
        // for(; i<n; i++){
        //     if(2*nums[i]<=target)ans++;
        // }

        
        return ans;
    }
};


/*

1, 3, 4, 5, 10 | target = 7

min = 1, max till 5 

1+2+4 => pow(2, p+1);



14*2=28
5*2=10=1
*/
56500