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$，但不需要输出这两个数。