Вуонг — один из величайших математиков всех времён! Его хобби — находить математические свойства всего на свете, а иногда даже несуществующих вещей! На день рождения его друг-программист подарил ему двоичную строку $S$ длины $n$. Спустя некоторое время он обнаружил у $S$ два очень интересных свойства:

• $X(S)$: длина кратчайшей строки, которая не является подпоследовательностью $S$.

• $Y(S)$: количество строк длины $X(S)$, которые не являются подпоследовательностями $S$.

Увидев, как Вуонгу понравилось находить эти два свойства, его друг-программист подумал, что было бы здорово немного поизменять строку $S$. Программист последовательно выполнит $q$ модификаций строки $S$. Каждая модификация относится к одному из следующих типов:

• 0 l r: присвоить элементам $S_l,S_{l+1},\ldots,S_r$ значение $0$.

• 1 l r: присвоить элементам $S_l,S_{l+1},\ldots,S_r$ значение $1$.

• F l r: инвертировать $S_l,S_{l+1},\ldots,S_r$. То есть для каждого $l\le i\le r$, если $S_i$ равно $0$, присвоить ему $1$, иначе присвоить ему $0$.

И конечно же, для каждой изменённой версии $S$ Вуонг также с радостью находил $X(S)$ и $Y(S)$, ведь это был его день рождения!

Но головоломка не полна без ответа. По заданной строке $S$ и списку из $q$ модификаций строки $S$ помогите другу-программисту найти $X(S)$ и $Y(S)$ после каждой модификации, чтобы он мог сверить результаты Вуонга с ответом.

Так как ответ может быть очень большим, выведите его по модулю $10^9+7$.

Строка $a$ называется подпоследовательностью строки $b$, если $a$ можно получить из $b$ удалением нескольких (возможно, ни одного или всех) символов. Например, bd, acd, b являются подпоследовательностями abcd, а da — нет.

Входные данные

Первая строка содержит два целых числа $n,q$ ($1\le n,q\le100\,000$) — длину строки $S$ и количество модификаций.

Вторая строка содержит двоичную строку $S$ длины $n$.

В $i$-й из следующих $q$ строк содержится описание $i$-й операции в одном из следующих форматов:

• 0 l r ($1\le l\le r\le n$): присвоить элементам $S_l,S_{l+1},\ldots,S_r$ значение $0$.

• 1 l r ($1\le l\le r\le n$): присвоить элементам $S_l,S_{l+1},\ldots,S_r$ значение $1$.

• F l r ($1\le l\le r\le n$): инвертировать $S_l,S_{l+1},\ldots,S_r$.

Выходные данные

Для каждой модификации строки $S$ выведите в отдельной строке два целых числа $X(S)$ и $Y(S)$ по модулю $10^9+7$.

Примеры

Входные данные 1

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

Выходные данные 1

1 1
2 1
3 4

Примечание

В примере строка $S$ равна 0110, и над $S$ выполняется $q=3$ модификации.

В следующей таблице показан процесс модификации строки $S$.

• Для $S=$ 0000 имеем $X(S)=1$ и $Y(S)=1$, так как существует ровно одна строка длины $1$, не являющаяся подпоследовательностью $S$, а именно строка 1.

• Для $S=$ 0011 строка 10 является кратчайшей и единственной строкой длины $2$, которая не является подпоследовательностью $S$.

• Для $S=$ 0101 список строк наименьшей длины, не являющихся подпоследовательностями $S$, имеет вид {000, 100, 110, 111}.

• Для начальной строки $S=$ 0110 список строк наименьшей длины, не являющихся подпоследовательностями $S$, имеет вид {000, 001, 100, 101, 111}. Поэтому $X(S)=3$ и $Y(S)=5$, но эти числа выводить не нужно.