Vuong jest jednym z największych matematyków wszech czasów! Jego hobby to odkrywanie matematycznych własności wszystkiego, czasami nawet rzeczy nieistniejących! Na urodziny jego przyjaciel programista podarował mu ciąg binarny $S$ długości $n$. Po pewnym czasie odkrył dwie bardzo ciekawe własności $S$:

• $X(S)$ — długość najkrótszego ciągu, który nie jest podciągiem $S$.

• $Y(S)$ — liczba ciągów długości $X(S)$, które nie są podciągami $S$.

Widząc, że Vuong dobrze się bawi odkrywając te dwie własności, przyjaciel programista pomyślał, że warto też nieco zmieniać ciąg $S$. Wykona kolejno $q$ modyfikacji $S$, każdą jednego z następujących typów:

• 0 l r — ustaw $S_l,S_{l+1},\ldots,S_r$ na $0$.

• 1 l r — ustaw $S_l,S_{l+1},\ldots,S_r$ na $1$.

• F l r — odwróć $S_l,S_{l+1},\ldots,S_r$. To znaczy, dla $l\le i\le r$, jeśli $S_i$ wynosi $0$, ustaw je na $1$; w przeciwnym razie na $0$.

Oczywiście Vuong chętnie znajdzie $X(S)$ i $Y(S)$ także dla każdej zmodyfikowanej wersji $S$, bo przecież to jego urodziny!

Jednak zagadka nie jest kompletna bez odpowiedzi. Mając ciąg $S$ i listę $q$ jego modyfikacji, pomóż przyjacielowi programiście znaleźć $X(S)$ i $Y(S)$ po każdej modyfikacji, aby mógł porównać wynik Vuonga z odpowiedzią.

Ponieważ odpowiedź może być bardzo duża, wypisz ją modulo $10^9+7$.

Ciąg $a$ jest podciągiem $b$, jeśli można go otrzymać z $b$ przez usunięcie kilku (być może zera lub wszystkich) znaków. Na przykład bd, acd i b są podciągami abcd, a da nie jest.

Wejście

Pierwszy wiersz zawiera dwie liczby całkowite $n,q$ ($1\le n,q\le100\,000$) — długość ciągu $S$ i liczbę modyfikacji.

Drugi wiersz zawiera ciąg binarny $S$ długości $n$.

$i$-ty z kolejnych $q$ wierszy opisuje $i$-tą operację w jednej z następujących postaci:

• 0 l r ($1\le l\le r\le n$) — ustaw $S_l,S_{l+1},\ldots,S_r$ na $0$.

• 1 l r ($1\le l\le r\le n$) — ustaw $S_l,S_{l+1},\ldots,S_r$ na $1$.

• F l r ($1\le l\le r\le n$) — odwróć $S_l,S_{l+1},\ldots,S_r$.

Wyjście

Dla każdej modyfikacji $S$ wypisz w jednym wierszu dwie liczby całkowite $X(S)$ i $Y(S)$ modulo $10^9+7$.

Przykład

Wejście 1

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

Wyjście 1

1 1
2 1
3 4

Uwagi

W przykładzie ciąg $S$ to 0110 i wykonywane są $q=3$ jego modyfikacje.

Poniższa tabela pokazuje modyfikacje $S$.

• Dla $S=$ 0000 mamy $X(S)=1$ i $Y(S)=1$, ponieważ istnieje jeden ciąg długości $1$, który nie jest podciągiem $S$: ciąg 1.

• Dla $S=$ 0011 ciąg 10 jest najkrótszy i jest jedynym ciągiem długości $2$, który nie jest podciągiem $S$.

• Dla $S=$ 0101 lista najkrótszych ciągów, które nie są podciągami $S$, to {000, 100, 110, 111}.

• Dla początkowego ciągu $S=$ 0110 lista najkrótszych ciągów, które nie są podciągami $S$, to {000, 001, 100, 101, 111}. Zatem $X(S)=3$ i $Y(S)=5$, ale nie trzeba wypisywać tych liczb.