<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:
    long mod = 1e9+7;
    long findPow(int x){
        long temp=1;
        long ans=1;
        if(x==1){
            return x;
        }
        // x = (n>=0 ? x : 1/x);
        long long m=abs(x);
        if(m==1)
            return x;
        while(m > 1)
        {
            if(m%2==0)
            {
                x*=x;
                ans=x;
                ans%=mod;
                m/=2;
            }
            else
            {
                temp*=x;
                temp%=mod;
                m-=1;
            }
        }
        ans*=temp;
        return ans%mod;
    }
    int numSubseq(vector<int>& nums, int target) {
        
        long ans =0 , n = nums.size();
        sort(begin(nums),  end(nums));
        vector<int>pow2(n+1,1);
        for(int i=1;i<=n;i++)
        {
            pow2[i]=(2*pow2[i-1])%mod;
        }
        for(int i = 0 ; i < n && nums[i] <= target;i++){
            int find = target-nums[i];

            int ub = upper_bound(nums.begin(),  nums.end() , find) - nums.begin(); 
            // if(ub < n && nums[ub] == find)ub++;
            cout << find << " " << ub << " ";
            int len = ub-i-1;

            if(len>=0)
                ans = (ans +pow2[len])%mod;
            cout << i << " " << len << " " << ans << endl;
        }
        return ans;
    }
};
53900