問題文

PCT 君は以下のような問題を作りました。

Lazy Segment Tree

$0$ で初期化された長さ $N$ の数列 $A_0,A_1,\dots,A_{N-1}$ があります。

数列 $A$ に対して $Q$ 個のクエリを処理してください。クエリは以下の $2$ 形式のどちらかです。

• $1\ L_i\ R_i\ (0 \leqq L_i < R_i \leqq N) \cdots$ $L_i \leqq j < R_i$ を満たす $j$ に対して $A_j$ を $1-A_j$ に変更する。
• $2\ L_i\ R_i\ (0 \leqq L_i < R_i \leqq N) \cdots$ $A_{L_i}$ から $A_{R_i-1}$ の転倒数を出力する。

この問題は Nyaan さんにはあまりにも簡単だったため、PCT 君は問題を以下のように変更しました。

Lazy Segment Tree...?

$N,Q$ が与えられた時 Lazy Segment Tree の入力としてあり得るものは $(N(N+1))^Q$ 通り存在しますが、その全てに対しての「出力する値の総和」の総和を $998244353$ で割ったあまりを求めてください。

Lazy Segment Tree...? を解いてください。

制約

• 入力は全て整数である。
• $2 \le N,Q \le 2 \times 10^5$

入力

$N\ Q$

出力

答えを $1$ 行に出力してください。

サンプル

2 2

1

1 0 1
2 0 2

4 5

1747840

1234 5678

492570703