P11891 [XRCOI Round 1] B. Talking About a Good Harvest Amid the Fragrance of Rice Flowers

**Add a more formal problem statement.** > Talking about a good harvest amid the fragrance of rice flowers, listening to a chorus of frogs.

In a rice field there are frogs of two types: $0$ and $1$. They line up into two columns, $a$ and $b$. Genius_Star noticed these frogs, so he decided to split the two frog sequences into arbitrary segments **with the same start and end positions**. Define the neatness of a segment as: $$ T(l,r) = \sum_{i=l}^r [a_i \ne b_i] $$ Here, $[A]$ equals $1$ if proposition $A$ is true, otherwise $0$. Then the happiness value brought to Genius_Star by segment $[l,r]$ is: $$ W(l,r) = T(l,r) \times \Big(A(l,r) + B(l,r) \Big) $$ where: $A(l,r)$ is the number of subsequences of type $01$ contained in interval $[l,r]$ of sequence $a$. $B(l,r)$ is the number of subsequences of type $10$ contained in interval $[l,r]$ of sequence $b$. The happiness value of a segmentation plan is the sum of the happiness values of all its segments. You need to compute the sum $s$ of the happiness values over **all** segmentation plans. Suppose the sequences are split into $k$ segments, and the $i$-th segment is $[l_i, r_i](l_i \le r_i)$. The following must hold: - $l_1 = 1, r_k = n$. - $\forall i \in[1, k), r_i + 1 = l_{i + 1}$. Two segmentation plans are different if and only if they have different numbers of segments, or there exists some $i$ such that $[l_i, r_i] \ne [l'_i, r'_i]$. Since Genius_Star cannot be too happy, you also need to take the answer modulo $10^9+7$. ### Formal statement Given two sequences $a,b$, define: - $T(l,r)$ as the number of positions in interval $[l,r]$ where $a_i\neq b_i$. - $A(l,r)$ as the number of subsequences of type $01$ in interval $[l,r]$ of sequence $a$. - $B(l,r)$ as the number of subsequences of type $10$ in interval $[l,r]$ of sequence $b$. - $ W(l,r) = T(l,r) \times \Big(A(l,r) + B(l,r) \Big) $. Here, a subsequence of type $xy$ means selecting two elements from left to right in the interval (**not necessarily contiguous**), where the first number is $x$ and the second number is $y$. Two subsequences are different if and only if the position of $x$ or the position of $y$ is different. Now you need to split the two sequences into arbitrary segments **with the same start and end positions**, and compute the sum, over all splitting methods, of the total $W$ of all segments. Since the answer may be very large, output it modulo $10^9+7$.

The first line contains two positive integers $n,op$. When $op=0$, the values $a_i,b_i$ for this test are **given directly**: - The next $n$ lines each contain two integers $a_i,b_i$. When $op=1$, the values $a_i,b_i$ for this test will be **generated in a special way**: - The second line contains five integers $x_1, y_1, z_1, f_1, f_2$. - The third line contains five integers $x_2, y_2, z_2, g_1, g_2$. Then $f_i,g_i(i \ge 3)$ satisfy: $$f_i = (f_{i-2} \times x_1 + f_{i-1} \times y_1 + z_1) \bmod 2^{64}$$ $$g_i = (g_{i-2} \times x_2 + g_{i-1} \times y_2 + z_2) \bmod 2^{64}$$ Then: - The value of $a_i$ is the $((i-1 \bmod 64)+1)$-th bit from low to high in the binary representation of $f_{\lfloor \frac{i-1}{64} \rfloor+3}$. - The value of $b_i$ is the $((i-1 \bmod 64)+1)$-th bit from low to high in the binary representation of $g_{\lfloor \frac{i-1}{64} \rfloor+3}$. **The above generation method is only to reduce input size; the standard algorithm does not depend on it.**

Output one line with an integer $s$, meaning the sum of the happiness values of all segmentation plans.

### Sample explanation #1: Only when splitting as $[1,3]$, we have $W(1,3)=1$. ### Sample explanation #4: We can obtain: $$f_1=1,f_2=1,f_3=2$$ $$g_1=1,g_2=1,g_3=3$$ Thus: $$(f_3)_2 = (00010)_2$$ $$(g_3)_2 = (00011)_2$$ Then: $$a = \{0,1,0,0,0\}$$ $$b = \{1,1,0,0,0\}$$ So the answer is $22$. ### Constraints **This problem uses bundled tests.** Subtask $0$ is the sample and is worth $0$ points. | Subtask ID | $n$ | $op$ | Special Property | Points | | :--------: | :-----------------: | :--: | :--------------: | :----: | | $1$ | $\leq 100$ | $=0$ | None | $5$ | | $2$ | $\leq 10^4$ | $=0$ | None | $10$ | | $3$ | $\leq 10^6$ | $=0$ | $A$ | $10$ | | $4$ | $\leq 10^6$ | $=0$ | $B$ | $10$ | | $5$ | $\leq 10^6$ | $=1$ | None | $25$ | | $6$ | $\leq 5\times 10^7$ | $=1$ | None | $40$ | Special property $A$: $T(l,r) = r-l+1$. Special property $B$: there exists exactly one $x$ such that $a_x \ne b_x$. For $100\%$ of the testdata, it is guaranteed that $1 \le n \le 5\times 10^7,1 \le x_1,x_2,y_1,y_2,z_1,z_2,f_1,f_2,g_1,g_2 \le 10^{18}$. Translated by ChatGPT 5