お知らせ

問題文に分かりづらい箇所が複数あったため、コンテスト中に修正を行いました（21:58）。

問題文

$(1,2,…,N)$ を並び替えて得られる数列 $P = (P_1,P_2,...,P_N)$ のうち以下の $2$ つの条件をすべて満たすものの個数を求め、$998244353$ で割ったあまりを出力してください。

1. すべての $i (1 ≤ i ≤ Q)$ において以下の条件が成り立つ。
• すべての $j (L_i ≤ j ≤ R_i)$ において $(P_{L_i}$ から $P_j$ までの偶数の個数 $) \leq ( P_{L_i}$ から $P_j$ までの奇数の個数 $)$ を満たす。
• $( P_{L_i}$ から $P_{R_i}$ までの偶数の個数 $) = ( P_{L_i}$ から $P_{R_i}$ までの奇数の個数 $)$ を満たす。
2. すべての $k (1 ≤ k ≤ N)$ において $( P_1$ から $P_k$ までの偶数の個数 $) \leq ( P_1$ から $P_k$ までの奇数の個数 $)$ を満たす。

入力

$N\ Q$
$L_1\  R_1$
$L_2\ R_2$
$\hspace{0.4cm}\vdots$
$L_Q\ R_Q$

・$1 \le N \le 2\times10^5\\$ ・$0 \le Q \le 60\\$ ・$1 \le L_i\le R_i \le N\\$ ・入力はすべて整数

出力

個数を $998244353$ で割ったあまりを出力せよ。

サンプル

4 1
1 2

4

7 2
1 4
2 6

0

13496 8
9414 12593
5086 6861
7912 8981
448 9427
11018 12581
1836 8405
8042 9605
3722 9873

262975011