¡Vuong es uno de los mayores matemáticos de todos los tiempos! Su afición es descubrir propiedades matemáticas de todo, ¡a veces incluso de cosas que no existen! En su cumpleaños, su amigo programador le regaló una cadena binaria $S$ de longitud $n$. Al cabo de un rato descubrió dos propiedades muy interesantes de $S$:
$X(S)$: la longitud de la cadena más corta que no es una subsecuencia de $S$.
$Y(S)$: el número de cadenas de longitud $X(S)$ que no son subsecuencias de $S$.
Al ver que Vuong disfrutaba descubriendo estas dos propiedades, su amigo programador pensó que también sería divertido cambiar un poco la cadena $S$. El programador hará secuencialmente $q$ modificaciones, cada una de uno de los tipos siguientes:
0 l r: establece $S_l,S_{l+1},\ldots,S_r$ en $0$.1 l r: establece $S_l,S_{l+1},\ldots,S_r$ en $1$.F l r: invierte $S_l,S_{l+1},\ldots,S_r$. Es decir, para $l\le i\le r$, si $S_i$ es $0$, cámbialo a $1$; en caso contrario, a $0$.
Y, por supuesto, Vuong también estaba encantado de hallar $X(S)$ e $Y(S)$ para cada versión modificada de $S$, ¡porque era su cumpleaños!
Pero un acertijo no está completo sin una respuesta. Dadas la cadena $S$ y la lista de $q$ modificaciones, ayuda al amigo programador a hallar $X(S)$ e $Y(S)$ después de cada modificación para comprobar los resultados de Vuong.
Como la respuesta puede ser muy grande, imprímela módulo $10^9+7$.
Una cadena $a$ es subsecuencia de una cadena $b$ si se puede obtener eliminando varios caracteres de $b$ (posiblemente ninguno o todos). Por ejemplo, bd, acd y b son subsecuencias de abcd, pero da no lo es.
Entrada
La primera línea contiene dos enteros $n,q$ ($1\le n,q\le100\,000$), la longitud de $S$ y el número de modificaciones.
La segunda línea contiene la cadena binaria $S$ de longitud $n$.
La línea $i$ de las siguientes $q$ líneas describe la operación $i$ en una de las formas siguientes:
0 l r($1\le l\le r\le n$): establece $S_l,S_{l+1},\ldots,S_r$ en $0$.1 l r($1\le l\le r\le n$): establece $S_l,S_{l+1},\ldots,S_r$ en $1$.F l r($1\le l\le r\le n$): invierte $S_l,S_{l+1},\ldots,S_r$.
Salida
Para cada modificación de $S$, imprime en una línea dos enteros $X(S)$ e $Y(S)$ módulo $10^9+7$.
Ejemplos
Entrada 1
4 3 0110 0 2 3 1 3 4 F 2 3
Salida 1
1 1 2 1 3 4
Nota
En el ejemplo, la cadena $S$ es 0110 y hay $q=3$ modificaciones.
La tabla siguiente muestra las modificaciones de $S$.
| Orden | Modificación | Valor de $S$ | $X(S)$ | $Y(S)$ |
|---|---|---|---|---|
| Inicial | 0110 |
$3$ | $5$ | |
| $1$ | 0 2 3 |
0000 |
$1$ | $1$ |
| $2$ | 1 3 4 |
0011 |
$2$ | $1$ |
| $3$ | F 2 3 |
0101 |
$3$ | $4$ |
Para $S=$
0000, $X(S)=1$ e $Y(S)=1$, porque hay una sola cadena de longitud $1$ que no es subsecuencia de $S$:1.Para $S=$
0011, la cadena10es la más corta y la única de longitud $2$ que no es subsecuencia de $S$.Para $S=$
0101, la lista de cadenas más cortas que no son subsecuencias de $S$ es{000, 100, 110, 111}.Para la cadena inicial $S=$
0110, la lista de cadenas más cortas que no son subsecuencias de $S$ es{000, 001, 100, 101, 111}. Por tanto, $X(S)=3$ e $Y(S)=5$, pero no tienes que imprimir estos números.