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

Submit

Login to submit.

Statistics

44% Solution Ratio
riyad000Earliest, Jun '20
nusuBotFastest, 0.0s
YouKnowWhoLightest, 524 kB
riyad000Shortest, 3585B
Toph uses cookies. By continuing you agree to our Cookie Policy.