P15557 [CCPC 2025 Harbin Site] 1-2-Bitwise OR Subsequence Problem

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**.

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.

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

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