問題文

0と1のみからなる長さ $N$ の文字列 $S_1S_2\ldots S_{N}$ があります。クエリが $Q$ 個与えられるので、与えられた順番に処理してください。

クエリは次の $2$ 種類のいずれかです。

• 1 l r : （削除クエリ） $l \leq i \leq r$ を満たす全ての $i$ について $S_i$ を文字_に変える。
• 2 l r : （数え上げクエリ） 自然数である文字列であって、$S$ の連続部分列 $S[l:r]$ の（連続とは限らない）部分列として現れるものが何種類あるか求める。自然数である文字列とは以下の条件を満たす文字列 $X$ のことを指す。
  • $X$ は空文字列ではない。
  • $X_1$ は 0でない。（つまりleading-zeroを認めない）
  • $X_1,X_2,\ldots,X_{|X|}$ はいずれも _でない。

クエリ2で求める種類数はとても大きな値になる場合があるので素数 $998244353$ で割った余りを出力してください。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $Q$
$S$
$query_1$
$query_2$
$\vdots$
$query_Q$

$1 \leq N \leq 6\times10^4$

$1 \leq Q \leq 6\times10^4$

$S_1,S_2,\ldots,S_N$ はすべて0または1

また各 $query_i$ は以下のどちらかの形で与えられる。

$1$ $l$ $r$

$2$ $l$ $r$

$1 \leq l \leq r \leq N$

入力はすべて整数

注釈

出題時から問題文を少し変更しました。「整数である文字列」としていたものを「自然数である文字列」に変更してあります。名称のみの変更で題意やテストケースへの変更はありません。(2024/05/18 04:20)

出力

クエリ2の個数を $K$ 個として、$K$ 行出力せよ。 $i$ 行目には $i$ 個目のクエリ2に対する答えを出力せよ。ただし素数 $998244353$ で割った余りを出力すること。

サンプル

4 3
1010
2 1 4
1 2 2
2 1 4

7
4

12 11
100000011100
1 3 3
2 6 8
2 8 11
2 12 12
2 3 9
2 1 2
1 2 9
2 2 9
1 6 6
1 5 10
2 3 7

1
6
0
2
2
0
0