6155：Subsequence Count

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

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$

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