Vuong är en av tidernas främsta matematiker! Hans hobby är att ta reda på matematiska egenskaper hos allt, och ibland till och med hos saker som inte existerar! På sin födelsedag gav hans programmerarvän honom en binär sträng $S$ av längd $n$. Efter ett tag upptäckte han två mycket intressanta egenskaper hos $S$:

• $X(S)$: längden på den kortaste strängen som inte är en delsekvens av $S$.

• $Y(S)$: antalet strängar av längd $X(S)$ som inte är en delsekvens av $S$.

När hans programmerarvän såg hur roligt Vuong hade när han tog reda på dessa två egenskaper, tänkte han att det vore toppen att också ändra strängen $S$ lite grann. Programmeraren kommer sekventiellt att göra $q$ ändringar i strängen $S$. Varje ändring är av en av följande typer:

• 0 l r: sätt $S_l,S_{l+1},\ldots,S_r$ till $0$.

• 1 l r: sätt $S_l,S_{l+1},\ldots,S_r$ till $1$.

• F l r: invertera $S_l,S_{l+1},\ldots,S_r$. Det vill säga, för $l\le i\le r$, om $S_i$ är $0$, sätt det till $1$, annars sätt det till $0$.

Och naturligtvis tyckte Vuong att det var lika roligt att hitta $X(S)$ och $Y(S)$ för varje ändrad version av $S$, eftersom det var hans födelsedag!

Men ett pussel är inte komplett utan ett facit. Givet strängen $S$ och listan med $q$ ändringar av strängen $S$, hjälp programmerarvännen att hitta $X(S)$ och $Y(S)$ för varje ändring, så att han kan kontrollera Vuongs resultat mot facit.

Eftersom svaret kan bli mycket stort, skriv ut svaret modulo $10^9+7$.

En sträng $a$ är en delsekvens av en sträng $b$ om $a$ kan erhållas från $b$ genom att ta bort flera (möjligen noll eller alla) tecken. Till exempel är bd, acd, b delsekvenser av abcd, medan da inte är det.

Indata

Den första raden innehåller två heltal $n,q$ ($1\le n,q\le100\,000$) — längden på strängen $S$ och antalet ändringar.

Den andra raden innehåller den binära strängen $S$ av längd $n$.

Den $i$-te raden bland de följande $q$ raderna innehåller beskrivningen av den $i$-te operationen på en av följande former:

• 0 l r ($1\le l\le r\le n$): sätt $S_l,S_{l+1},\ldots,S_r$ till $0$.

• 1 l r ($1\le l\le r\le n$): sätt $S_l,S_{l+1},\ldots,S_r$ till $1$.

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

Utdata

För varje ändring av $S$, skriv ut på en rad två heltal $X(S)$ och $Y(S)$ modulo $10^9+7$.

Exempel

Indata 1

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

Utdata 1

1 1
2 1
3 4

Förklaring

I exemplet är strängen $S$ lika med 0110, och det görs $q=3$ ändringar av $S$.

Följande tabell visar ändringarna av $S$.

• För $S=$ 0000 är $X(S)=1$ och $Y(S)=1$, eftersom det finns exakt en sträng av längd $1$ som inte är en delsekvens av $S$, nämligen strängen 1.

• För $S=$ 0011 är strängen 10 den kortaste, och är den enda strängen av längd $2$ som inte är en delsekvens av $S$.

• För $S=$ 0101 är listan över de kortaste strängarna som inte är delsekvenser av $S$ lika med {000, 100, 110, 111}.

• För den ursprungliga strängen $S=$ 0110 är listan över de kortaste strängarna som inte är delsekvenser av $S$ lika med {000, 001, 100, 101, 111}. Alltså är $X(S)=3$ och $Y(S)=5$, men du behöver inte skriva ut dessa tal.