Problem Description

You are given a sequence $a_1,a_2,\ldots,a_n$ of length $n$ that contains only $1$ and $2$ ($a_i \in \{1,2\}$). You may perform the following operation any number of times:

• Choose $1 \le i < n$, delete $a_i$ and $a_{i+1}$ from the sequence, and insert $a_i | a_{i+1}$ at their original position, where $|$ denotes bitwise OR.
• Note that after each operation, the value of $n$ decreases by $1$.

For example, if $a=[1,2,1]$ and you choose $i=2$ to operate, then after the operation the sequence becomes $a=[1,3]$.

After performing some operations, how many essentially different sequences can be produced? Output the result modulo $10^9+7$. Two sequences are different if and only if their lengths are different, or there exists some position where the numbers differ.

Since $n$ may be very large, the sequence is given in a run-length compressed format, where equal numbers are compressed into segments. In particular, it is guaranteed that the lengths of the segments of equal numbers are monotonically non-decreasing from left to right.

Input Format

The first line contains an integer $T$ ($1 \le T \le 10^6$), the number of test cases.

Then each test case is given as follows:

The first line contains two integers $m,a_1$ ($1 \le m \le 10^6, 1 \le a_1 \le 2$), representing the number of segments, and the value of $a_1$.

The second line contains $m$ integers $l_1,l_2,\ldots,l_m$ ($1 \leq l_1 \leq l_2 \leq \ldots \leq l_m \leq 10^9$), where $l_i$ is the length of the $i$-th segment in the sequence.

Since adjacent segments have different values, the length-$n$ sequence, where $n=\sum\limits_{i=1}^m l_i$, can be uniquely determined by $a_1$ and $l_1,l_2,\ldots,l_m$.

It is guaranteed that $\sum m \le 10^6$ over all test cases.

Output Format

For each test case, output one integer, the answer modulo $10^9+7$.

2
3 1
1 1 2
8 2
1 2 3 4 5 6 7 8

7
2961300

Hint

In Sample 1, the sequence represented by the first test case is $a=[1,2,1,1]$. After performing some operations, the essentially different sequences that can be obtained are:

• $[1,2,1]$.
• $[1,2,1,1]$.
• $[1,3]$.
• $[1,3,1]$.
• $[3]$.
• $[3,1]$.
• $[3,1,1]$.

Translated by ChatGPT 5