骨牌涂色

• 时间限制：2 秒
• 内存限制：512 MiB

题目描述

有 $N$ 个格子，编号为 $1$ 到 $N$。最初所有格子都没有被涂色。

有 $M$ 种颜色。第 $i$ 种颜色只能用于区间 $[L_i,R_i]$ 内的格子。每个格子至多涂一种颜色，也可以不涂色。

求满足下列条件的涂色方案数，对 $998244353$ 取模：

• 对每个已涂色的格子 $i$，格子 $i-1$ 与 $i+1$ 中恰有一个格子和它颜色相同。
• 格子 $0$ 与格子 $N+1$ 视为没有涂色。

换言之，每段同色连续块的长度必须恰好为 $2$；同一种颜色可以在不相邻的位置再次使用。

输入格式

N M
L_1 R_1
L_2 R_2
...
L_M R_M

输出格式

输出一个整数，表示合法涂色方案数对 $998244353$ 取模后的结果。

样例输入 1

5 2
1 3
1 5

样例输出 1

11

样例解释 1

第一种颜色可用于格子 $1,2,3$，第二种颜色可用于格子 $1,2,3,4,5$，共有 $11$ 种合法方案。

样例输入 2

3 3
1 1
2 2
3 3

样例输出 2

1

样例解释 2

每种颜色都无法覆盖两个相邻格子，因此只有全部不涂色这一种方案。

样例输入 3

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

样例输出 3

775503999

数据范围

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