<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>

// Idea: (1) reverse thinking: what subseqs are bad?
//    instead of "what are good subseqs?"
// (2) sort the array.
// (3) if a number x >= target, then x cannot appear in any good subseq,
//     because the min element >= 1. So we should exclude such x directly.
// (4) as for numbers that <= target / 2:
//     all subseqs from them are valid, good.
//     So they can form 2^k - 1 good subseqs (power set), where k is the count.
// (5) for number y = (target - 1) to appear in a good subseq, the subseq
//     has to contain 1, and the subseq can freely contain any number
//     x that 1 <= x <= y. (power set)
// (6) for number y = (target - 2) to appear in a good subseq, the subseq
//     has to contain 1 or 2, and the subseq can freely contain any number
//     x that 1 <= x <= y, or 2 <= x <= y (power set)
class Solution {
    constexpr const static int ModBase = 1'000'000'007;

    static long long powerOfTwoMod(int n) {
        static vector<long long> ps{1, 2, 4, 8, 16, 32, 64, 128};
        if (n < ps.size()) {
            return ps[n];
        }
        while (ps.size() < n + 1) {
            ps.push_back(ps.back() * 2 % ModBase);
        }
        return ps[n];
    }

    // the range sum
    static long long sumOfPowerOfTwoMod(int from, int to) {
        static vector<long long> prefixSum{1, 3, 7, 15, 31};
        assert(from <= to);
        if (to + 1 >= prefixSum.size()) {
            for (int i = prefixSum.size(); i <= to; ++i) {
                prefixSum.push_back((prefixSum[i - 1] + powerOfTwoMod(i)) %
                                    ModBase);
            }
        }
        return (ModBase + prefixSum[to] -
                (from <= 0 ? 0 : prefixSum[from - 1])) %
               ModBase;
    }

public:
    int numSubseq(vector<int>& A, int target) {
        sort(A.begin(), A.end()); // sort it
        // pop out the numbers that are too big to be useful
        while (!A.empty() && A.back() >= target) {
            A.pop_back();
        }
        if (A.empty()) { // nothing left
            return 0;
        }
        const int n = A.size();
        long long res = 0;
        // two pointers algorithm: j1 < j2
        for (int i = n - 1, j2 = 0; i >= 0 && A[i] > target / 2; --i) {
            const int buddy = target - A[i];
            if (A[0] > buddy) {
                continue; // skip
            }
            while (A[j2] <= buddy) {
                ++j2;
            }
            // now we can use A[i] as maxElem, and use each of A[0...j2) as
            // minElem
            // cout << "computing the sum of 2**" << i - 1 << " + ... + 2**"
            //      << i - j2 + 1 - 1 << endl;
            // for (int k = 0; k < j2; ++k) {
            //     res += powerOfTwoMod(i - k - 1);
            //     res %= ModBase;
            // }
            res += sumOfPowerOfTwoMod(i - j2, i - 1);
            res %= ModBase;
        }
        // find the numbers that <= target/2, because they can freely combine
        // to form good subseq
        auto iter = upper_bound(A.begin(), A.end(), target / 2);
        int cntFreeNums = iter - A.begin();
        if (cntFreeNums > 0) {
            cout << "Found " << cntFreeNums << " freely combinable numbers"
                 << endl;
            res += powerOfTwoMod(cntFreeNums) - 1; // -1 is for the empty set
            res %= ModBase;
        }

        return res;
    }
};
55800