Vuong on yksi kaikkien aikojen suurimmista matemaatikoista! Hänen harrastuksensa on selvittää kaikenlaisten asioiden matemaattisia ominaisuuksia, ja joskus jopa olemattomien asioiden! Syntymäpäivänään hänen ohjelmoijaystävänsä antoi hänelle binäärimerkkijonon $S$, jonka pituus on $n$. Hetken kuluttua hän löysi merkkijonosta $S$ kaksi erittäin mielenkiintoista ominaisuutta:

• $X(S)$: lyhimmän sellaisen merkkijonon pituus, joka ei ole merkkijonon $S$ alijono.

• $Y(S)$: sellaisten pituutta $X(S)$ olevien merkkijonojen lukumäärä, jotka eivät ole merkkijonon $S$ alijonoja.

Nähdessään kuinka hauskaa Vuongilla oli näiden kahden ominaisuuden selvittämisessä, hänen ohjelmoijaystävänsä ajatteli, että olisi hienoa myös muuttaa merkkijonoa $S$ hieman. Ohjelmoija tekee peräkkäin $q$ muokkausta merkkijonoon $S$. Jokainen muokkaus on yhtä seuraavista tyypeistä:

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

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

• F l r: käännä bittien $S_l,S_{l+1},\ldots,S_r$ arvot. Toisin sanoen kaikilla $l\le i\le r$, jos $S_i$ on $0$, aseta se arvoksi $1$, muuten aseta se arvoksi $0$.

Ja tietenkin jokaiselle muokatulle merkkijonon $S$ versiolle Vuong etsi myös mielellään arvot $X(S)$ ja $Y(S)$, koska oli hänen syntymäpäivänsä!

Mutta pulma ei ole täydellinen ilman vastausta. Annettuna merkkijono $S$ ja lista merkkijonoon $S$ tehtävistä $q$ muokkauksesta, auta ohjelmoijaystävää löytämään $X(S)$ ja $Y(S)$ jokaiselle muokkaukselle, jotta hän voi tarkistaa Vuongin tuloksen vastauksen avulla.

Koska vastaus voi olla hyvin suuri, tulosta vastaus modulo $10^9+7$.

Merkkijono $a$ on merkkijonon $b$ alijono, jos $a$ voidaan saada merkkijonosta $b$ poistamalla useita (mahdollisesti nolla tai kaikki) merkkejä. Esimerkiksi bd, acd, b ovat merkkijonon abcd alijonoja, kun taas da ei ole.

Syöte

Ensimmäinen rivi sisältää kaksi kokonaislukua $n,q$ ($1\le n,q\le100\,000$) — merkkijonon $S$ pituuden ja muokkausten lukumäärän.

Toinen rivi sisältää pituutta $n$ olevan binäärimerkkijonon $S$.

Seuraavien $q$ rivin $i$-s rivi sisältää $i$-nnen operaation kuvauksen yhdessä seuraavista muodoista:

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

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

• F l r ($1\le l\le r\le n$): käännä bittien $S_l,S_{l+1},\ldots,S_r$ arvot.

Tuloste

Tulosta jokaiselle merkkijonon $S$ muokkaukselle omalle rivilleen kaksi kokonaislukua $X(S)$ ja $Y(S)$ modulo $10^9+7$.

Esimerkit

Syöte 1

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

Tuloste 1

1 1
2 1
3 4

Selitys

Esimerkissä merkkijono $S$ on 0110, ja merkkijonoon $S$ tehdään $q=3$ muokkausta.

Seuraava taulukko havainnollistaa merkkijonon $S$ muokkauksia.

• Kun $S=$ 0000, $X(S)=1$ ja $Y(S)=1$, koska on olemassa tasan yksi pituutta $1$ oleva merkkijono, joka ei ole merkkijonon $S$ alijono, nimittäin merkkijono 1.

• Kun $S=$ 0011, merkkijono 10 on lyhin ja ainoa pituutta $2$ oleva merkkijono, joka ei ole merkkijonon $S$ alijono.

• Kun $S=$ 0101, lista lyhimmistä merkkijonoista, jotka eivät ole merkkijonon $S$ alijonoja, on {000, 100, 110, 111}.

• Alkuperäiselle merkkijonolle $S=$ 0110 lista lyhimmistä merkkijonoista, jotka eivät ole merkkijonon $S$ alijonoja, on {000, 001, 100, 101, 111}. Siispä $X(S)=3$ ja $Y(S)=5$, mutta näitä lukuja ei tarvitse tulostaa.