Vuongは史上最も偉大な数学者の1人です！彼の趣味は、あらゆるもの、時には存在しないものの数学的性質さえ見つけることです！誕生日に、プログラマーの友人が長さ $n$ の二進文字列 $S$ を贈りました。しばらくして、彼は $S$ のとても興味深い2つの性質を見つけました。

• $X(S)$：$S$ の部分列ではない最短の文字列の長さ。

• $Y(S)$：長さが $X(S)$ で、$S$ の部分列ではない文字列の数。

Vuongが2つの性質を見つけて楽しんでいるのを見て、プログラマーの友人は文字列 $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$ と $q$ 回の変更のリストが与えられたとき、各変更後の $X(S)$ と $Y(S)$ を求め、プログラマーの友人がVuongの結果を答えと照合できるように手伝ってください。

答えは非常に大きくなることがあるため、$10^9+7$ で割った余りを出力してください。

文字列 $b$ からいくつかの文字（0文字でもすべてでもよい）を削除して文字列 $a$ を得られる場合、$a$ は $b$ の部分列です。例えば bd、acd、b は abcd の部分列ですが、da は違います。

入力

最初の行には、文字列 $S$ の長さと変更回数を表す2つの整数 $n,q$ ($1\le n,q\le100\,000$) が含まれます。

2行目には長さ $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$ で割った余りである2つの整数を1行に出力してください。

入出力例

入力 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 の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$ ですが、これらを出力する必要はありません。