問題文

以下の条件を全て満たす数列 $A=(A_1,\dots ,A_N)$ として考えられるものの個数を $998244353$ で割ったあまりを求めてください。

• $A$ の要素は $1$ 以上 $K$ 以下の整数からなり、要素数は $N$ である。
• $i=1,2,\dots ,M$ の全てに対して、以下を満たす。
  • $L_i\le A_j\le R_i$ を満たす整数 $j(1\le j\le N)$ が存在する。

入力

$NK$
$M$
$L_1{R}_1$
$⋮$
$L_M{R}_M$

• $1\le N\le {10}^9$
• $1\le K\le 1500$
• $1\le M\le min(2\times {10}^5,{\displaystyle \frac{K(K+1)}{2}})$
• $1\le L_i\le R_i\le K$
• $i\ne j$ ならば $(L_i,R_i)\ne (L_j,R_j)$
• 入力は全て整数

出力

答えを $mod998244353$ で出力せよ。

サンプル

2 5
2
1 3
4 5

12

2 5
2
1 3
3 4

13

2 12
3
1 2
3 6
7 11

0

924844033 1500
6
1 314
159 265
358 979
271 818
1123 1349
1499 1500

520302805