Vuong er en av tidenes største matematikere! Hobbyen hans er å finne ut matematiske egenskaper ved alt mulig, og noen ganger til og med ved ting som ikke eksisterer! På bursdagen hans ga programmerervennen hans ham en binærstreng $S$ med lengde $n$. Etter en stund fant han ut to svært interessante egenskaper ved $S$:

• $X(S)$: lengden på den korteste strengen som ikke er en delsekvens av $S$.

• $Y(S)$: antallet strenger med lengde $X(S)$ som ikke er en delsekvens av $S$.

Da programmerervennen så hvor gøy Vuong hadde det med å finne disse to egenskapene, tenkte han at det ville vært flott å endre litt på strengen $S$ også. Programmereren vil sekvensielt gjøre $q$ endringer på strengen $S$. Hver endring er av en av følgende typer:

• 0 l r: sett $S_l,S_{l+1},\ldots,S_r$ til $0$.

• 1 l r: sett $S_l,S_{l+1},\ldots,S_r$ til $1$.

• F l r: inverter $S_l,S_{l+1},\ldots,S_r$. Det vil si, for $l\le i\le r$, hvis $S_i$ er $0$, sett det til $1$, ellers sett det til $0$.

Og selvfølgelig, for hver endrede versjon av $S$, syntes Vuong det var like gøy å finne $X(S)$ og $Y(S)$, fordi det var bursdagen hans!

Men en gåte er ikke komplett uten en fasit. Gitt strengen $S$ og listen over $q$ endringer på strengen $S$, hjelp programmerervennen med å finne $X(S)$ og $Y(S)$ for hver endring, slik at han kan sjekke Vuongs resultat mot fasiten.

Fordi svaret kan bli svært stort, vennligst skriv ut svaret modulo $10^9+7$.

En streng $a$ er en delsekvens av en streng $b$ hvis $a$ kan oppnås fra $b$ ved å slette flere (muligens null eller alle) tegn. For eksempel er bd, acd, b delsekvenser av abcd, mens da ikke er det.

Inndata

Den første linjen inneholder to heltall $n,q$ ($1\le n,q\le100\,000$) — lengden på strengen $S$ og antallet endringer.

Den andre linjen inneholder binærstrengen $S$ med lengde $n$.

Den $i$-te linjen på de neste $q$ linjene inneholder beskrivelsen av den $i$-te operasjonen på en av følgende former:

• 0 l r ($1\le l\le r\le n$): sett $S_l,S_{l+1},\ldots,S_r$ til $0$.

• 1 l r ($1\le l\le r\le n$): sett $S_l,S_{l+1},\ldots,S_r$ til $1$.

• F l r ($1\le l\le r\le n$): inverter $S_l,S_{l+1},\ldots,S_r$.

Utdata

For hver endring av $S$, skriv ut på en linje to heltall $X(S)$ og $Y(S)$ modulo $10^9+7$.

Eksempler

Inndata 1

4 3
0110
0 2 3
1 3 4
F 2 3

Utdata 1

1 1
2 1
3 4

Forklaring

I eksempelet er strengen $S$ lik 0110, og det er $q=3$ endringer på $S$.

Følgende tabell viser endringene av $S$.

• For $S=$ 0000 er $X(S)=1$ og $Y(S)=1$, fordi det finnes én streng med lengde $1$ som ikke er en delsekvens av $S$, nemlig strengen 1.

• For $S=$ 0011 er strengen 10 den korteste, og er den eneste strengen med lengde $2$ som ikke er en delsekvens av $S$.

• For $S=$ 0101 er listen over strenger av korteste lengde som ikke er delsekvenser av $S$ lik {000, 100, 110, 111}.

• For startstrengen $S=$ 0110 er listen over strenger av korteste lengde som ikke er delsekvenser av $S$ lik {000, 001, 100, 101, 111}. Så $X(S)=3$ og $Y(S)=5$, men du trenger ikke å skrive ut disse tallene.