问题描述

有 $N$ 个格子，编号从 $1$ 到 $N$。初始时，没有任何格子被染色。

有 $M$ 种颜色，第 $i$ 种颜色可以用来涂染区间 $L_i, L_i+1, \ldots, R_i$ 中任意数量的格子。

求满足以下条件的涂色方案数对 $998244353$ 取模后的结果：

• 对于每个格子 $i$，如果该格子被染成某种颜色，则恰好有 $i-1$ 和 $i+1$ 中的一个格子被涂成与格子 $i$ 相同的颜色。
  • 其中，格子 $0$ 和格子 $N+1$ 视为未被染色。

约束条件

• $1\leq N,M \leq 5\times 10^5$
• $1\leq L_i \leq R_i \leq N$
• 所有输入值均为整数。

输入

输入从标准输入给出，格式如下：

$N$ $M$
$L_1$ $R_1$
$\vdots$
$L_M$ $R_M$

5 2
1 3
1 5

11

3 3
1 1
2 2
3 3

1

500000 10
1 499999
2 499998
3 499997
4 499996
5 499995
6 499994
7 499993
8 499992
9 499991
10 499990

775503999