Vuong là một trong những nhà toán học vĩ đại nhất mọi thời đại! Sở thích của anh ấy là tìm ra các tính chất toán học của mọi thứ, và đôi khi ngay cả của những thứ không tồn tại! Vào ngày sinh nhật của anh ấy, người bạn lập trình viên đã tặng anh một xâu nhị phân $S$ có độ dài $n$. Sau một lúc, anh ấy đã tìm ra hai tính chất rất thú vị của $S$:
$X(S)$: độ dài của xâu ngắn nhất mà không phải là một xâu con của $S$.
$Y(S)$: số lượng xâu có độ dài $X(S)$ mà không phải là xâu con của $S$.
Thấy Vuong rất thích thú khi tìm ra hai tính chất này, người bạn lập trình viên nghĩ rằng sẽ thật tuyệt nếu thay đổi xâu $S$ một chút. Lập trình viên sẽ lần lượt thực hiện $q$ phép biến đổi trên xâu $S$. Mỗi phép biến đổi thuộc một trong các loại sau:
0 l r: gán $S_l,S_{l+1},\ldots,S_r$ thành $0$.1 l r: gán $S_l,S_{l+1},\ldots,S_r$ thành $1$.F l r: lật $S_l,S_{l+1},\ldots,S_r$. Tức là, với $l\le i\le r$, nếu $S_i$ là $0$ thì gán nó thành $1$, ngược lại gán nó thành $0$.
Và tất nhiên, với mỗi phiên bản đã biến đổi của $S$, Vuong cũng rất vui vẻ tìm $X(S)$ và $Y(S)$, bởi vì đó là ngày sinh nhật của anh ấy!
Nhưng một câu đố sẽ không trọn vẹn nếu thiếu đáp án. Cho xâu $S$ và danh sách $q$ phép biến đổi trên xâu $S$, hãy giúp người bạn lập trình viên tìm $X(S)$ và $Y(S)$ cho mỗi phép biến đổi, để anh ấy có thể kiểm tra kết quả của Vuong với đáp án.
Vì đáp án có thể rất lớn, hãy in ra đáp án theo modulo $10^9+7$.
Một xâu $a$ là một xâu con của xâu $b$ nếu $a$ có thể thu được từ $b$ bằng cách xóa đi một số (có thể là không xóa hoặc xóa tất cả) ký tự. Ví dụ, bd, acd, b là các xâu con của abcd, trong khi da thì không.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên $n,q$ ($1\le n,q\le100\,000$) — độ dài của xâu $S$ và số lượng phép biến đổi.
Dòng thứ hai chứa xâu nhị phân $S$ có độ dài $n$.
Dòng thứ $i$ trong $q$ dòng tiếp theo chứa mô tả của thao tác thứ $i$ dưới một trong các dạng sau:
0 l r($1\le l\le r\le n$): gán $S_l,S_{l+1},\ldots,S_r$ thành $0$.1 l r($1\le l\le r\le n$): gán $S_l,S_{l+1},\ldots,S_r$ thành $1$.F l r($1\le l\le r\le n$): lật $S_l,S_{l+1},\ldots,S_r$.
Kết quả
Với mỗi phép biến đổi của $S$, in ra trên một dòng hai số nguyên $X(S)$ và $Y(S)$ theo modulo $10^9+7$.
Ví dụ
Dữ liệu vào 1
4 3 0110 0 2 3 1 3 4 F 2 3
Kết quả 1
1 1 2 1 3 4
Giải thích
Trong ví dụ, xâu $S$ là 0110, và có $q=3$ phép biến đổi trên $S$.
Bảng dưới đây minh họa các phép biến đổi của $S$.
| Thứ tự | Phép biến đổi | Giá trị của $S$ | $X(S)$ | $Y(S)$ |
|---|---|---|---|---|
| Ban đầu | 0110 |
$3$ | $5$ | |
| $1$ | 0 2 3 |
0000 |
$1$ | $1$ |
| $2$ | 1 3 4 |
0011 |
$2$ | $1$ |
| $3$ | F 2 3 |
0101 |
$3$ | $4$ |
Với $S=$
0000, $X(S)=1$ và $Y(S)=1$, bởi vì có đúng một xâu độ dài $1$ không phải là xâu con của $S$, đó là xâu1.Với $S=$
0011, xâu10là ngắn nhất, và là xâu duy nhất có độ dài $2$ không phải là xâu con của $S$.Với $S=$
0101, danh sách các xâu có độ dài ngắn nhất không phải là xâu con của $S$ là{000, 100, 110, 111}.Với xâu ban đầu $S=$
0110, danh sách các xâu có độ dài ngắn nhất không phải là xâu con của $S$ là{000, 001, 100, 101, 111}. Do đó $X(S)=3$ và $Y(S)=5$, nhưng bạn không cần phải in ra hai số này.