Vuong 係有史以嚟最偉大嘅數學家之一！佢嘅興趣係搵出萬事萬物嘅數學性質，有時甚至包括唔存在嘅嘢！喺佢生日嗰日，佢嘅程式員朋友送咗一個長度為 $n$ 嘅二進制字串 $S$ 畀佢。過咗一陣，佢發現咗 $S$ 嘅兩個好有趣嘅性質：

• $X(S)$：唔係 $S$ 嘅子序列嘅最短字串嘅長度。

• $Y(S)$：長度為 $X(S)$ 而且唔係 $S$ 嘅子序列嘅字串數量。

見到 Vuong 咁享受搵呢兩個性質，佢嘅程式員朋友覺得稍微修改一下字串 $S$ 都會幾好玩。程式員會依次對 $S$ 進行 $q$ 次修改。每次修改屬於以下類型之一：

• 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$ 嘅每個修改後嘅版本，Vuong 都好樂意去搵 $X(S)$ 同 $Y(S)$，因為今日係佢生日！

不過，謎題冇答案就唔完整。畀定字串 $S$ 同埋對 $S$ 嘅 $q$ 次修改列表，請幫程式員朋友求出每次修改後嘅 $X(S)$ 同 $Y(S)$，等佢可以用答案嚟核對 Vuong 嘅結果。

由於答案可能好大，請輸出答案對 $10^9+7$ 取模嘅結果。

如果字串 $a$ 可以透過從字串 $b$ 入面刪除若干個字元（可以唔刪，亦可以全部刪除）得到，就稱 $a$ 係 $b$ 嘅子序列。例如，bd、acd、b 都係 abcd 嘅子序列，而 da 唔係。

輸入格式

第一行包含兩個整數 $n,q$ ($1\le n,q\le100\,000$)，代表字串 $S$ 嘅長度同修改次數。

第二行包含長度為 $n$ 嘅二進制字串 $S$。

接落嚟嘅 $q$ 行入面，第 $i$ 行包含第 $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$，但唔需要輸出呢兩個數。