注釈

この問題は、以下の問題を題材に解きやすく改題したものです。
https://codeforces.com/contest/1767/problem/C

問題文

整数$N$および$M$個の制約$[l_i, r_i] (0 \leq i < M)$が与えられます。
$0, 1$のみからなる長さ$N$の数列であって、以下の条件を満たすものの個数を$998244353$で割った余りを出力してください。

条件
全ての$0 \leq i < M$について、数列の$l_i$番目から$r_i$番目には$0$と$1$の両方が含まれる。

制約

• $2 \leq N \leq 1000$
• $0 \leq M \leq \frac{N (N-1)}{2}$
• $1 \leq l_i < r_i \leq N \quad (0 \leq i < M)$

入力

N M
l0 r0
l1 r1
…
l(M-1) r(M-1)

出力

答えを1行で出力せよ。

サンプル

3 2
1 2
2 3

2

条件を満たす数列は[1, 0, 1]、[0, 1, 0]の2通りです。
[0, 0, 1]、[1, 1, 1]などは、いずれも条件を満たしません。

4 2
1 3
2 4

10

以下の10通りです。

• [0, 0, 1, 0]
• [0, 0, 1, 1]
• [0, 1, 0, 0]
• [0, 1, 0, 1]
• [0, 1, 1, 0]
• [1, 0, 0, 1]
• [1, 0, 1, 0]
• [1, 0, 1, 1]
• [1, 1, 0, 0]
• [1, 1, 0, 1]

2 0

4

条件が一つも与えられない場合もあります。

50 6
46 48
3 41
13 45
4 21
10 29
2 5

59926715

$998244353$で割った余りを出力してください。