Vuong è uno dei più grandi matematici di tutti i tempi! Il suo passatempo è scoprire le proprietà matematiche di ogni cosa, e talvolta persino di cose che non esistono! Per il suo compleanno, il suo amico programmatore gli ha regalato una stringa binaria $S$ di lunghezza $n$. Dopo un po', ha scoperto due proprietà molto interessanti di $S$:
$X(S)$: la lunghezza della stringa più corta che non è una sottosequenza di $S$.
$Y(S)$: il numero di stringhe di lunghezza $X(S)$ che non sono sottosequenze di $S$.
Vedendo che Vuong si divertiva a trovare queste due proprietà, il suo amico programmatore ha pensato che sarebbe stato fantastico modificare anche un po' la stringa $S$. Il programmatore eseguirà in sequenza $q$ modifiche sulla stringa $S$. Ogni modifica è di uno dei seguenti tipi:
0 l r: imposta $S_l,S_{l+1},\ldots,S_r$ a $0$.1 l r: imposta $S_l,S_{l+1},\ldots,S_r$ a $1$.F l r: inverti $S_l,S_{l+1},\ldots,S_r$. Cioè, per $l\le i\le r$, se $S_i$ è $0$, impostalo a $1$, altrimenti impostalo a $0$.
E naturalmente, per ogni versione modificata di $S$, Vuong è stato ben felice di trovare $X(S)$ e $Y(S)$, perché era il suo compleanno!
Ma un rompicapo non è completo senza una soluzione. Data la stringa $S$ e l'elenco delle $q$ modifiche alla stringa $S$, aiuta l'amico programmatore a trovare $X(S)$ e $Y(S)$ per ciascuna modifica, in modo che possa controllare il risultato di Vuong con la soluzione.
Poiché la risposta può essere molto grande, stampa la risposta modulo $10^9+7$.
Una stringa $a$ è una sottosequenza di una stringa $b$ se $a$ può essere ottenuta da $b$ cancellando diversi caratteri (eventualmente zero o tutti). Ad esempio, bd, acd, b sono sottosequenze di abcd, mentre da non lo è.
Dati di ingresso
La prima riga contiene due interi $n,q$ ($1\le n,q\le100\,000$) — la lunghezza della stringa $S$ e il numero di modifiche.
La seconda riga contiene la stringa binaria $S$ di lunghezza $n$.
La $i$-esima delle successive $q$ righe contiene la descrizione della $i$-esima operazione in una delle seguenti forme:
0 l r($1\le l\le r\le n$): imposta $S_l,S_{l+1},\ldots,S_r$ a $0$.1 l r($1\le l\le r\le n$): imposta $S_l,S_{l+1},\ldots,S_r$ a $1$.F l r($1\le l\le r\le n$): inverti $S_l,S_{l+1},\ldots,S_r$.
Dati di uscita
Per ogni modifica di $S$, stampa su una riga due interi $X(S)$ e $Y(S)$ modulo $10^9+7$.
Esempi
Dati di ingresso 1
4 3 0110 0 2 3 1 3 4 F 2 3
Dati di uscita 1
1 1 2 1 3 4
Note
Nell'esempio, la stringa $S$ è 0110 e ci sono $q=3$ modifiche a $S$.
La tabella seguente mostra le modifiche di $S$.
| Ordine | Modifica | Valore di $S$ | $X(S)$ | $Y(S)$ |
|---|---|---|---|---|
| Iniziale | 0110 |
$3$ | $5$ | |
| $1$ | 0 2 3 |
0000 |
$1$ | $1$ |
| $2$ | 1 3 4 |
0011 |
$2$ | $1$ |
| $3$ | F 2 3 |
0101 |
$3$ | $4$ |
Per $S=$
0000, $X(S)=1$ e $Y(S)=1$, perché c'è una sola stringa di lunghezza $1$ che non è una sottosequenza di $S$, ovvero la stringa1.Per $S=$
0011, la stringa10è la più corta ed è l'unica stringa di lunghezza $2$ che non è una sottosequenza di $S$.Per $S=$
0101, l'elenco delle stringhe di lunghezza minima che non sono sottosequenze di $S$ è{000, 100, 110, 111}.Per la stringa iniziale $S=$
0110, l'elenco delle stringhe di lunghezza minima che non sono sottosequenze di $S$ è{000, 001, 100, 101, 111}. Quindi $X(S)=3$ e $Y(S)=5$, ma non è necessario stampare questi numeri.