Vuong adalah salah satu matematikawan terhebat sepanjang masa! Hobinya adalah mencari tahu sifat-sifat matematika dari segala sesuatu, dan terkadang bahkan dari hal-hal yang tidak ada! Pada hari ulang tahunnya, teman pemrogramnya memberinya sebuah string biner $S$ dengan panjang $n$. Setelah beberapa saat, ia menemukan dua sifat yang sangat menarik dari $S$:

• $X(S)$: panjang dari string terpendek yang bukan merupakan subsekuens dari $S$.

• $Y(S)$: banyaknya string dengan panjang $X(S)$ yang bukan merupakan subsekuens dari $S$.

Melihat Vuong bersenang-senang menemukan kedua sifat ini, teman pemrogramnya berpikir bahwa akan sangat bagus jika string $S$ juga diubah sedikit. Pemrogram tersebut secara berurutan akan melakukan $q$ modifikasi pada string $S$. Setiap modifikasi merupakan salah satu dari jenis berikut:

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

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

• F l r: balikkan $S_l,S_{l+1},\ldots,S_r$. Yaitu, untuk $l\le i\le r$, jika $S_i$ bernilai $0$, ubah menjadi $1$; jika tidak, ubah menjadi $0$.

Dan tentu saja, untuk setiap versi $S$ yang telah dimodifikasi, Vuong juga dengan senang hati mencari $X(S)$ dan $Y(S)$, karena ini adalah hari ulang tahunnya!

Namun sebuah teka-teki tidak lengkap tanpa jawaban. Diberikan string $S$ dan daftar $q$ modifikasi pada string $S$, bantulah teman pemrogram tersebut mencari $X(S)$ dan $Y(S)$ untuk setiap modifikasi, sehingga ia dapat memeriksa hasil Vuong dengan jawabannya.

Karena jawabannya bisa sangat besar, keluarkan jawaban modulo $10^9+7$.

Sebuah string $a$ merupakan subsekuens dari string $b$ jika $a$ dapat diperoleh dari $b$ dengan menghapus beberapa (mungkin nol atau semua) karakter. Sebagai contoh, bd, acd, b adalah subsekuens dari abcd, sedangkan da bukan.

Masukan

Baris pertama berisi dua bilangan bulat $n,q$ ($1\le n,q\le100\,000$) — panjang string $S$ dan banyaknya modifikasi.

Baris kedua berisi string biner $S$ dengan panjang $n$.

Baris ke-$i$ dari $q$ baris berikutnya berisi deskripsi operasi ke-$i$ dalam salah satu bentuk berikut:

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

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

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

Keluaran

Untuk setiap modifikasi pada $S$, keluarkan dalam satu baris dua bilangan bulat $X(S)$ dan $Y(S)$ modulo $10^9+7$.

Contoh

Masukan 1

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

Keluaran 1

1 1
2 1
3 4

Penjelasan

Pada contoh, string $S$ adalah 0110, dan terdapat $q=3$ modifikasi pada $S$.

Tabel berikut menunjukkan modifikasi pada $S$.

• Untuk $S=$ 0000, $X(S)=1$ dan $Y(S)=1$, karena hanya ada satu string dengan panjang $1$ yang bukan merupakan subsekuens dari $S$, yaitu string 1.

• Untuk $S=$ 0011, string 10 adalah yang terpendek, dan merupakan satu-satunya string dengan panjang $2$ yang bukan merupakan subsekuens dari $S$.

• Untuk $S=$ 0101, daftar string dengan panjang terpendek yang bukan merupakan subsekuens dari $S$ adalah {000, 100, 110, 111}.

• Untuk string awal $S=$ 0110, daftar string dengan panjang terpendek yang bukan merupakan subsekuens dari $S$ adalah {000, 001, 100, 101, 111}. Jadi $X(S)=3$ dan $Y(S)=5$, tetapi Anda tidak perlu mencetak kedua bilangan ini.