Vuong est l'un des plus grands mathématiciens de tous les temps ! Son passe-temps consiste à découvrir les propriétés mathématiques de tout, et parfois même de choses qui n'existent pas ! Pour son anniversaire, son ami programmeur lui a offert une chaîne binaire $S$ de longueur $n$. Au bout d'un moment, il a découvert deux propriétés très intéressantes de $S$ :

• $X(S)$ : la longueur de la plus courte chaîne qui n'est pas une sous-séquence de $S$.

• $Y(S)$ : le nombre de chaînes de longueur $X(S)$ qui ne sont pas des sous-séquences de $S$.

Voyant que Vuong s'amusait à trouver ces deux propriétés, son ami programmeur s'est dit qu'il serait génial de modifier également un peu la chaîne $S$. Le programmeur effectuera séquentiellement $q$ modifications sur la chaîne $S$. Chaque modification est de l'un des types suivants :

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

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

• F l r : inverser $S_l,S_{l+1},\ldots,S_r$. C'est-à-dire que pour $l\le i\le r$, si $S_i$ vaut $0$, on le met à $1$, sinon on le met à $0$.

Et bien sûr, pour chaque version modifiée de $S$, Vuong s'est également fait un plaisir de trouver $X(S)$ et $Y(S)$, car c'était son anniversaire !

Mais une énigme n'est pas complète sans sa réponse. Étant donné la chaîne $S$ et la liste des $q$ modifications apportées à la chaîne $S$, aidez l'ami programmeur à trouver $X(S)$ et $Y(S)$ pour chaque modification, afin qu'il puisse vérifier le résultat de Vuong avec la réponse.

Comme la réponse peut être très grande, veuillez afficher la réponse modulo $10^9+7$.

Une chaîne $a$ est une sous-séquence d'une chaîne $b$ si $a$ peut être obtenue à partir de $b$ en supprimant plusieurs caractères (éventuellement zéro ou tous). Par exemple, bd, acd, b sont des sous-séquences de abcd, tandis que da ne l'est pas.

Entrée

La première ligne contient deux entiers $n,q$ ($1\le n,q\le100\,000$) — la longueur de la chaîne $S$ et le nombre de modifications.

La deuxième ligne contient la chaîne binaire $S$ de longueur $n$.

La $i$-ème des $q$ lignes suivantes contient la description de la $i$-ème opération sous l'une des formes suivantes :

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

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

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

Sortie

Pour chaque modification de $S$, affichez sur une ligne deux entiers $X(S)$ et $Y(S)$ modulo $10^9+7$.

Exemples

Entrée 1

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

Sortie 1

1 1
2 1
3 4

Note

Dans l'exemple, la chaîne $S$ est 0110, et il y a $q=3$ modifications sur $S$.

Le tableau suivant illustre les modifications de $S$.

• Pour $S=$ 0000, $X(S)=1$ et $Y(S)=1$, car il existe une seule chaîne de longueur $1$ qui n'est pas une sous-séquence de $S$, à savoir la chaîne 1.

• Pour $S=$ 0011, la chaîne 10 est la plus courte, et c'est la seule chaîne de longueur $2$ qui n'est pas une sous-séquence de $S$.

• Pour $S=$ 0101, la liste des chaînes de longueur minimale qui ne sont pas des sous-séquences de $S$ est {000, 100, 110, 111}.

• Pour la chaîne initiale $S=$ 0110, la liste des chaînes de longueur minimale qui ne sont pas des sous-séquences de $S$ est {000, 001, 100, 101, 111}. Ainsi $X(S)=3$ et $Y(S)=5$, mais vous n'avez pas besoin d'afficher ces deux nombres.