Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Sum of Medians

By curly_braces · Limits 2s, 1.0 GB

You will be given an array of size $n$ where all elements of the array are pairwise distinct. You will choose at most $k$ pairwise different subsequences from the array in such a way that the sum of medians in all those subsequences is maximized.

Your task is to find out the maximum possible sum of the medians.

Input

Input starts with an integer $T(0 < T \leq 1000)$ denoting number of test cases.

Each test case starts with two integers, $n(0 < n \leq 10^5)$ and $k (0 < k < min(2^n,10^{18}))$.

All elements of the array are pairwise distinct and in the range $[-10^9, 10^9]$.

The sum of $n$ in all test cases don’t exceed $5 \times 10^5$.

Subtask Constraints

Subtask 1 (10% of points)

$0 < n ≤ 2$
$k = 2^n - 1$
All elements of the array are in the range $[0, 10]$
The sum of $n$ in all test cases don’t exceed $100$.

Subtask 2 (20% of points)

$0 < n ≤ 16$
$k = 2^n - 1$
All elements of the array are in the range $[0, 10^4]$
The sum of $n$ in all test cases don’t exceed $10^5$

Subtask 3 (40% of points)

$0 < n ≤ 32$
$k < 2^n$
All elements of the array are in the range $[-10^5, 10^5]$
The sum of $n$ in all test cases don’t exceed $10^5$

Subtask 4 (100% of points)

Original constraints

Output

For each test case, print an integer containing the answer to that test case. As the result can be big, print it modulo $10^9 + 7$.

Sample

InputOutput
1
6 9
2 1 3 6 5 4
44

Notes

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. We say one subsequence is different from another one if at least one number is present in one of the sequence but not in the other.

Median of a subsequence of length $l$ is $\frac{l + 1}{2}$ th element after sorting. For example, Median of $[2, 4,1,3]$ is $2$ and median of $[1,3,4,5,2]$ is $3$.

    Discussion

    Statistics


    29% Solution Ratio

    riyad000Earliest, 1M ago

    YouKnowWhoFastest, 0.0s

    YouKnowWhoLightest, 524 kB

    riyad000Shortest, 3585B

    Submit

    Login to submit

    Editorial

    Subtask 1: You can hard code the results. Subtask 2: You can generate all possible subsequences and...