Vuong ist einer der größten Mathematiker aller Zeiten! Sein Hobby ist es, mathematische Eigenschaften von allem herauszufinden, und manchmal sogar von Dingen, die gar nicht existieren! An seinem Geburtstag schenkte ihm sein Programmierer-Freund eine Binärzeichenkette $S$ der Länge $n$. Nach einer Weile fand er zwei sehr interessante Eigenschaften von $S$ heraus:

• $X(S)$: die Länge der kürzesten Zeichenkette, die keine Teilfolge von $S$ ist.

• $Y(S)$: die Anzahl der Zeichenketten der Länge $X(S)$, die keine Teilfolge von $S$ sind.

Als sein Programmierer-Freund sah, wie viel Spaß Vuong beim Herausfinden dieser beiden Eigenschaften hatte, dachte er, dass es toll wäre, die Zeichenkette $S$ auch ein wenig zu verändern. Der Programmierer führt nacheinander $q$ Änderungen an der Zeichenkette $S$ durch. Jede Änderung gehört zu einer der folgenden Arten:

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

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

• F l r: invertiere $S_l,S_{l+1},\ldots,S_r$. Das heißt, für $l\le i\le r$: falls $S_i$ gleich $0$ ist, setze es auf $1$, andernfalls setze es auf $0$.

Und natürlich hat Vuong auch für jede geänderte Version von $S$ gerne $X(S)$ und $Y(S)$ bestimmt, schließlich war es sein Geburtstag!

Aber ein Rätsel ist ohne Lösung nicht vollständig. Gegeben die Zeichenkette $S$ und die Liste der $q$ Änderungen an der Zeichenkette $S$, hilf dem Programmierer-Freund, $X(S)$ und $Y(S)$ für jede Änderung zu finden, damit er Vuongs Ergebnis anhand der Lösung überprüfen kann.

Da die Antwort sehr groß sein kann, gib die Antwort bitte modulo $10^9+7$ aus.

Eine Zeichenkette $a$ ist eine Teilfolge einer Zeichenkette $b$, wenn $a$ aus $b$ durch Löschen mehrerer (möglicherweise null oder aller) Zeichen erhalten werden kann. Beispielsweise sind bd, acd, b Teilfolgen von abcd, während da keine ist.

Eingabe

Die erste Zeile enthält zwei ganze Zahlen $n,q$ ($1\le n,q\le100\,000$) — die Länge der Zeichenkette $S$ und die Anzahl der Änderungen.

Die zweite Zeile enthält die Binärzeichenkette $S$ der Länge $n$.

Die $i$-te der nächsten $q$ Zeilen enthält die Beschreibung der $i$-ten Operation in einer der folgenden Formen:

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

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

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

Ausgabe

Gib für jede Änderung von $S$ in einer Zeile zwei ganze Zahlen $X(S)$ und $Y(S)$ modulo $10^9+7$ aus.

Beispiele

Eingabe 1

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

Ausgabe 1

1 1
2 1
3 4

Hinweis

Im Beispiel ist die Zeichenkette $S$ gleich 0110, und es gibt $q=3$ Änderungen an $S$.

Die folgende Tabelle veranschaulicht die Änderungen an $S$.

• Für $S=$ 0000 gilt $X(S)=1$ und $Y(S)=1$, da es genau eine Zeichenkette der Länge $1$ gibt, die keine Teilfolge von $S$ ist, nämlich die Zeichenkette 1.

• Für $S=$ 0011 ist die Zeichenkette 10 die kürzeste und zugleich die einzige Zeichenkette der Länge $2$, die keine Teilfolge von $S$ ist.

• Für $S=$ 0101 lautet die Liste der kürzesten Zeichenketten, die keine Teilfolgen von $S$ sind, {000, 100, 110, 111}.

• Für die ursprüngliche Zeichenkette $S=$ 0110 lautet die Liste der kürzesten Zeichenketten, die keine Teilfolgen von $S$ sind, {000, 001, 100, 101, 111}. Also gilt $X(S)=3$ und $Y(S)=5$, aber diese beiden Zahlen müssen nicht ausgegeben werden.