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

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

11
6
8
10