Subsequence Count

Time Limit: 10000/5000 MS (Java/Others)

Memory Limit: 256000/256000 K (Java/Others)

Description

Given a binary string $S[1,...,N]$ (i.e. a sequence of 0's and 1's), and $Q$ queries on the string.

There are two types of queries:

1. Flipping the bits (i.e., changing all 1 to 0 and 0 to 1) between $l$ and $r$ (inclusive).
2. Counting the number of distinct subsequences in the substring $S[l,...,r]$.

Input

The first line contains an integer $T$, denoting the number of the test cases.

For each test, the first line contains two integers $N$ and $Q$.

The second line contains the string $S$.

Then $Q$ lines follow, each with three integers $type$, $l$ and $r$, denoting the queries.

$1\leq T\leq 5$

$1\leq N, Q\leq 10^5$

$S[i]\in \lbrace 0, 1 \rbrace, \forall 1\leq i\leq N$

$type\in \lbrace 1, 2 \rbrace$

$1\leq l \leq r\leq N$

Output

For each query of type 2, output the answer mod ($10^9+7$) in one line.

Sample Input

2 4 4 1010 2 1 4 2 2 4 1 2 3 2 1 4 4 4 0000 1 1 2 1 2 3 1 3 4 2 1 4

Sample Output

11 6 8 10

Hint

liuyiding

Source

2017中国大学生程序设计竞赛 - 网络选拔赛

提交代码