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