You are given a binary string, $s$, and you have to answer $q$ queries in order. 

A binary string is a string consisting of only 0's and 1's. 

There are two types of queries: 

• $1 \: i$ - Flip the character at position $i$ i.e $0$ becomes $1$, and $1$ becomes $0$. Each modification affects the subsequent queries i.e the queries are dependent. 
• $2 \: l \: r$ - Print the decimal value of the binary substring formed by indices in some range $[l, r]$. As the value could be very large, compute it modulo $10^9 + 7$.

The decimal value of some range $[l, r]$ in $s$ is $S_{l}2^{r - l} + S_{l + 1}2^{r - l - 1} + ... + S_{i}2^{r - i} + ... + S_{r}2^{0}$, where $S_{i}$ represents the integer value of the character at the $i^{th}$ position in $s$. 

Input format

• The first line of the input contains two integers, $n$ and $q$ - denoting the number of characters in the string $s$ and the number of queries. 
• The second line of the input contains the string $s$ - the string contains only 0's or 1's
• The next $q$ lines of the input contain two types of queries: 
  • $1 \: i$ - denoting a type 1 query and the index to be flipped.
  • $2 \: l \: r$ - denoting a type 2 query and the indices to find the decimal value modulo $10^9 + 7$.

Output format

For each of the type $2$ queries, output an integer denoting the decimal value of the binary representation of the queried range modulo $10^9 + 7$.

Constraints

$1 \leq n, q \leq 10^5 \\ 1 \leq i \leq n \\ 1 \leq l \leq r \leq n$