A-Alternating 2.0_"蔚来杯"2022牛客暑期多校训练营（加赛）

时间限制：C/C++/Rust/Pascal 4秒，其他语言8秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

Let's call a binary string (a string where each character is either 0 or 1) $x$ of length $k$ an alternating string if and only if $x_i \neq x_{i + 1}$ for all $i \in [1,k - 1]$ .

You can perform the following operation on a binary string $x$ of length $k$ :

Choose a substring $x_lx_{l + 1}\dots x_r$ and invert all characters of this substring, that is, replace $0$ by $1$ and vice versa.

Let's call beauty of a binary string $x$ the minimum number of operations that need to be performed on $x$ to make it an alternating string.

Now you are given a binary string $s$ of length $n$ .

You need to support $q$ queries. Each query is represented by two indices $l$ and $r$ , denoting that you have to calculate the sum of beauty of all $2^{r - l + 1} - 1$ non-empty subsequences of $s_ls_{l + 1}\dots s_r$ modulo $10^9 + 7$ .

The queries are given in a compressed format. Let $l_i$ and $r_i$ be the bounds for the $i$ -th query. For $i \in [1,q]$ , let $f = ((l_{i - 1} \cdot a_l + b_l) \bmod n ) + 1$ and $g = ((r_{i - 1} \cdot a_r + b_r) \bmod n ) + 1$ . If $f > g$ , they are swapped. Then assign $f$ to $l_i$ and $g$ to $r_i$ . The value of $a_l,b_l,a_r,b_r,l_0,r_0$ will be given in the input.

Let $ans_i$ be the answer modulo $10^9 + 7$ to the $i$ -th query. You need to output $\bigoplus\limits_{i = 1}^q (ans_i + 23 \cdot i) = (ans_1 + 23 \cdot 1) \oplus (ans_2 + 23 \cdot 2) \oplus \ldots \oplus (ans_q + 23 \cdot q)$ .

Here, $\oplus$ denotes the bitwise XOR operation.

String $x$ is a subsequence of string $y$ if and only if $x$ can be obtained from $y$ by deletion of several (possibly, zero) characters.

输入描述:

The first line contains two integers  () --- the length of the binary string  and the number of queries.

The second line contains a binary string  of length .

The third line contains six integers  () --- the parameters to generate the queries.

输出描述:

Print a single integer --- the value of .

示例1

输入

复制

3 2
001
0 0 1 0 1 1

输出

复制

说明

In the first query, , all non-empty subsequences of  are , beauty of which are  respectively, with the sum of .

In the second query, , all non-empty subsequences of  are , beauty of which are  respectively, with the sum of .

Thus, .