Moamen and XOR
Contest: Codeforces Round 737 (Div. 2)
Difficulty rating: 1700
Tags: bitmasks, combinatorics, dp, math, matrices

Moamen and Ezzat are playing a game. They create an array $$$a$$$ of $$$n$$$ non-negative integers where every element is less than $$$2^k$$$.

Moamen wins if $$$a_1 \,\&\, a_2 \,\&\, a_3 \,\&\, \ldots \,\&\, a_n \ge a_1 \oplus a_2 \oplus a_3 \oplus \ldots \oplus a_n$$$.

Here $$$\&$$$ denotes the bitwise AND operation, and $$$\oplus$$$ denotes the bitwise XOR operation.

Please calculate the number of winning for Moamen arrays $$$a$$$.

As the result may be very large, print the value modulo $$$1\,000\,000\,007$$$ ($$$10^9 + 7$$$).

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 5$$$)— the number of test cases.

Each test case consists of one line containing two integers $$$n$$$ and $$$k$$$ ($$$1 \le n\le 2\cdot 10^5$$$, $$$0 \le k \le 2\cdot 10^5$$$).

Output format:
For each test case, print a single value — the number of different arrays that Moamen wins with.

Print the result modulo $$$1\,000\,000\,007$$$ ($$$10^9 + 7$$$).

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example, $$$n = 3$$$, $$$k = 1$$$. As a result, all the possible arrays are $$$[0,0,0]$$$, $$$[0,0,1]$$$, $$$[0,1,0]$$$, $$$[1,0,0]$$$, $$$[1,1,0]$$$, $$$[0,1,1]$$$, $$$[1,0,1]$$$, and $$$[1,1,1]$$$.

Moamen wins in only $$$5$$$ of them: $$$[0,0,0]$$$, $$$[1,1,0]$$$, $$$[0,1,1]$$$, $$$[1,0,1]$$$, and $$$[1,1,1]$$$.

Example input:
3
3 1
2 1
4 0

Example output:
5
2
1

Editorial:
We can use dynamic programming to get the maximum number of rows that make a beautiful grid.
Define the 2d array, $$$dp$$$, where $$$dp_{i,j}$$$ $$$=$$$ maximum number of rows (from row $$$1$$$ to row $$$i$$$) that make a beautiful grid, and has $$$1$$$ in column $$$j$$$ at the last row.
Form the definition:
- $$$dp_{0,j}$$$ $$$=$$$ $$$0$$$.
- $$$dp_{i,j}$$$ $$$=$$$ $$$1$$$ $$$+$$$ $$$\max_{k \in C_i}$$$ $$$\{$$$ $$$dp_{i-1,k}$$$ $$$\}$$$ if $$$grid_{i,j}$$$ $$$=$$$ $$$1$$$.
- Otherwise, $$$dp_{i,j}$$$ $$$=$$$ $$$\max_{k \in C_i}$$$ $$$\{$$$ $$$dp_{i-1,k}$$$ $$$\}$$$.
where $$$C_i$$$ is that set of columns that contain $$$1$$$ in row $$$i$$$.
As you know, the set $$$C_i$$$ contains the intervals, so we just search in some intervals for the maximum, or update some intervals in the previous layer in $$$dp$$$. We can do it faster using [Segment tree](https://cp-algorithms.com/data_structures/segment_tree.html).
**So the algorithm will be as follows:**
- Define an array $$$prev$$$, where $$$prev_i$$$ $$$=$$$ the previous row of $$$i$$$ in which maximum beautiful grid end with $$$i$$$-th row. We will use it to get the rows that will not be removed.
- Build a segment tree of pairs ($$$value$$$, $$$index$$$) initially with $$$\{$$$ $$$0$$$ , $$$-1$$$ $$$\}$$$.
- Then for each $$$i$$$ from $$$1$$$ to $$$n$$$:
- Get the maximum value in all the ranges $$$[l_j,r_j]$$$ that contains $$$1$$$ at the $$$i$$$-th row. Let's call it $$$mx$$$.
- Store $$$prev_{i}$$$ $$$=$$$ $$$mx.index$$$.
- Update all the ranges $$$[l_j,r_j]$$$ of this row like this: $$$seg_j$$$ $$$=$$$ $$$max($$$ $$$seg_j$$$ $$$,$$$ $$$\{$$$ $$$mx.value$$$ $$$+$$$ $$$1$$$ $$$,$$$ $$$i$$$ $$$\})$$$.
- Finally, get the rows that has the maximum value using the $$$prev$$$ array, and remove the others.
The total complexity will be $$$\mathcal{O}(n + m\log{}10^9)$$$ or $$$\mathcal{O}(n + m\log{}m)$$$ if you make a coordinate compression to the values.