题目背景

增加形式化题意。

稻花香里说丰年，听取蛙声一片。

题目描述

稻田里有 $0$, $1$ 两种类型的青蛙。他们排成了 $a,b$ 两列。

Genius_Star 发现了这些青蛙，所以他决定将这两个青蛙队列分别划分为起止点相同的任意段，定义某一段的整齐度 $T$ 为：

其中 ：$[A]$ 表示若 $A$ 命题为真则为 $1$，否则为 $0$。

则对于段 $[l,r]$ 的带给 Genius_Star 的开心值为

其中：

$A(l,r)$ 表示在 $a$ 序列的 $[l,r]$ 区间中包含的 $01$ 类型的子序列数量。

$B(l,r)$ 表示在 $b$ 序列的 $[l,r]$ 区间中包含的 $10$ 类型的子序列数量。

一个分段方案带给 Genius_Star 的开心值是所有小段带给他的开心值之和，你需要求出所有的分段方案带给他的开心值之和 $s$。

设分为了 $k$ 段，第 $i$ 段为 $[l_i, r_i](l_i \le r_i)$，需要满足：

• $l_1 = 1, r_k = n$。

• $\forall i \in[1, k), r_i + 1 = l_{i + 1}$。

则若两个分段的方案不同，当且仅当两个方案分的段数不同或者存在一个 $i$ 使得 $[l_i, r_i] \ne[l'_i, r'_i]$。

由于 Genius_Star 不能过于开心，你还需要将答案对 $10^9+7$ 取模。

形式化题意

给定一个两个序列 $a,b$ 。定义

• $T(l,r)$ 为在区间 $[l,r]$ 中 $a_i\neq b_i$ 的个数。

• $A(l,r)$ 表示 $a$ 序列在 $[l,r]$ 区间中的 $01$ 类型子序列个数。

• $B(l,r)$ 表示 $b$ 序列在 $[l,r]$ 区间中的 $10$ 类型子序列个数。

• $W(l,r) = T(l,r) \times \Big(A(l,r) + B(l,r) \Big)$。

其中：$xy$ 类型子序列表示从区间左端点开始向右顺次选择两个元素（不要求连续），其中，第一个数是 $x$ ，第二个数是 $y$。两个子序列不同当且仅当 $x$ 或 $y$ 所在位置不同。

现在你需要将两个序列划分成起止点相同的任意段，求所有划分方式的每段的 $W$ 之和。

由于答案可能很大，你需要将答案对 $10^9+7$ 取模。

输入格式

第一行，两个正整数 $n,op$。

当 $op=0$ 时，则该测试点的 $a_i,b_i$ 直接给出：

• 接下来 $n$ 行，每行两个整数 $a_i,b_i$。

当 $op=1$ 时，则该测试点的 $a_i,b_i$ 将特殊生成：

• 第二行共五个整数 $x_1, y_1, z_1, f_1, f_2$。

• 第三行共五个整数 $x_2, y_2, z_2, g_1, g_2$。

则 $f_i,g_i(i \ge 3)$ 满足：

那么：

• $a_i$ 的值就是 $f_{\lfloor \frac{i-1}{64} \rfloor+3}$ 转化为二进制后从低位到高位第 $(i-1 \bmod 64)+1$ 位。

• $b_i$ 的值就是 $g_{\lfloor \frac{i-1}{64} \rfloor+3}$ 转化为二进制后从低位到高位第 $(i-1 \bmod 64)+1$ 位。

上述数据生成方式仅是为了减少输入量大小，标准算法不依赖于该生成方式。

输出格式

输出共一行。一个整数 $s$，表示所有的分段方案带给 Genius_Star 的开心值之和。

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

提示

样例解释 #1：

只有按照 $[1,3]$ 分段时，$W(1,3)=1$。

样例解释 #4：

可以得到：

得到：

则：

故答案为 $22$。

数据范围：

本题采用捆绑测试。

其中子任务 $0$ 为样例，记 $0$ 分。

特殊性质 $A$： $T(l,r) = r-l+1$。

特殊性质 $B$：有且仅有一个 $x$ 满足 $a_x \ne b_x$。

对于 $100 \%$ 的数据，保证 $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}$。