题目描述

给定一个长度为 $n$ 的只包含 $1$ 和 $2$ 的序列 $a_1,a_2,\ldots,a_n$ ($a_i \in \{1,2\}$)。你可以进行若干次如下操作：

• 选择 $1 \le i < n$，将 $a_i$ 和 $a_{i+1}$ 从序列中删除，并在它们的原来的位置添加为 $a_i | a_{i+1}$，其中 $|$ 表示按位或。
• 注意在每次操作后 $n$ 的大小会减 $1$。

例如若序列 $a=[1,2,1]$，选择对 $i=2$ 进行操作，操作后序列会变为 $a=[1,3]$。

求在进行若干次操作后，能产生多少种本质不同的序列，输出结果对 $10^9+7$ 的结果。两个序列不同当且仅当它们的长度不同或某个数不同。

$n$ 可能很大，因此序列会通过将相同数字压缩成同一段的格式输入。特别地，保证每一段相同数字的长度，从前往后单调不降。

输入格式

第一行输入一个整数 $T$ ($1 \le T \le 10^6$)，表示测试数据组数。

接下来依次给出每组测试数据，对于每组测试数据：

第一行输入两个整数 $m,a_1$ ($1 \le m \le 10^6, 1 \le a_1 \le 2$) 表示序列分成的段数，以及 $a_1$ 的值。

第二行输入 $m$ 个整数 $l_1,l_2,\ldots,l_m$ ($1 \leq l_1 \leq l_2 \leq \ldots \leq l_m \leq 10^9$)，其中 $l_i$ 表示序列中第 $i$ 段数的长度。

由于相邻的段内数的值不同，故可以通过 $a_1$ 和 $l_1,l_2,\ldots,l_m$ 唯一确定这个长度为 $n=\sum\limits_{i=1}^m l_i$ 的序列。

保证所有数据中的 $\sum m \le 10^6$。

输出格式

对于每组数据，输出一个整数表示答案对 $10^9+7$ 取模的结果。

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

7
2961300

提示

样例一中第一组测试数据表示的序列为 $a=[1,2,1,1]$，进行若干次操作后能表示出的本质不同的序列有：

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