Background

Add a more formal problem statement.

Talking about a good harvest amid the fragrance of rice flowers, listening to a chorus of frogs.

Problem Description

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

Input Format

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 Format

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

3 0
1 0
1 1
0 0

1

5 0
0 1
1 0
0 1
1 1
1 1

70

4 0
0 1
1 0
0 1
1 0

52

5 1
1 1 0 1 1
1 1 1 1 1

22

10000 1
1 1 0 1 1
1 1 1 1 1

559297012

Hint

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$			$10$
$3$	$\leq 10^6$		$A$
$4$			$B$
$5$		$=1$	None	$25$
$6$	$\leq 5\times 10^7$			$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