P15557 [CCPC 2025 哈尔滨站] 1-2-按位或子序列问题

给定一个长度为 $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$ 取模的结果。

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