Given a sequence $a_1, a_2, \dots, a_n$ of length $n$ containing only $1$ and $2$, you can perform the following operation any number of times:

• Choose $1 \le i < n$, remove $a_i$ and $a_{i+1}$ from the sequence, and insert $a_i \mid a_{i+1}$ at their original position, where $\mid$ denotes the bitwise OR operation. After each operation, the size of $n$ decreases by $1$.

For example, if the sequence is $a = [1, 2, 1]$, choosing $i = 2$ results in the sequence $a = [1, 3]$.

Calculate how many essentially different sequences can be produced after performing the operation any number of times. You need to output the answer modulo $10^9 + 7$. Two sequences are different if and only if they have different lengths or differ in at least one element.

Since $n$ can be very large, the sequence is provided in a compressed format where consecutive identical numbers are grouped together. Specifically, it is guaranteed that the lengths of each segment of identical numbers are non-decreasing from the beginning to the end.

Input

There are multiple test cases. The first line contains an integer $T$ ($1 \le T \le 10^6$) representing the number of test cases. For each test case:

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

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

Since adjacent segments have different values, the sequence of length $n = \sum_{i=1}^m l_i$ is uniquely determined by $a_1$ and $l_1, l_2, \dots, l_m$.

It is guaranteed that the sum of $m$ over all test cases does not exceed $10^6$.

Output

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

Examples

Input 1

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

Output 1

7
2961300

Note

In the first test case of the example, the sequence is $a = [1, 2, 1, 1]$. The essentially different sequences that can be produced after performing the operation any number of times are:

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