题目描述

小 Y 最近学会了如何用线段树维护序列，并支持区间求和的操作。

以下给出本题中线段树的定义。该定义可能和你熟知的线段树有区别。

线段树是一种有根的二叉树，其每个节点对应了序列上的一个区间 $[l, r)$，其中根节点对应 $[0, n)$。

对于每个节点，若其代表的序列区间 $[l, r)$ 满足 $r - l = 1$，则其为叶节点；否则存在整数 $m$ $(l < m < r)$，满足其左儿子代表区间 $[l, m)$，右儿子代表区间 $[m, r)$。

线段树的形态取决于每个非叶结点的划分点 $m$ 的选择。

在区间求和的问题上，对于序列 $a_0, a_1, \dots , a_{n-1}$，线段树的每个结点 $[l, r)$ 维护了 $(a_l + a_{l+1} + \cdots + a_{r-1})$ 的值。

小 J 有一个长度为 $N$ 的数组 $A_0, A_1, \dots , A_{N-1}$，他并不知道 $A$ 中的任何一个数，但是他有一棵线段树维护了 $A$ 的区间和。线段树由 $X_1, X_2, \dots , X_{N-1}$ 给出，其中 $X_i$ 是线段树先序遍历的第 $i$ 个非叶结点的划分点。

例如，如果 $N = 5$, $X = [2, 1, 4, 3]$，则线段树包含的结点的先序遍历为 $[0, 5)$, $[0, 2)$, $[0, 1)$, $[1, 2)$, $[2, 5)$, $[2, 4)$, $[2, 3)$, $[3, 4)$, $[4, 5)$。

小 J 有 $M$ 个区间 $[L_1, R_1)$, $[L_2, R_2)$, $\dots$, $[L_M, R_M)$，他想知道，在所有 $2^{2N-1}$ 个线段树结点的子集中，有多少个子集 $S$ 满足以下条件：

如果已知 $S$ 中所有结点维护的值，则每个 $[L_i, R_i)$ 区间的和都能被唯一确定。

例如，如果已知 $[0, 1)$, $[1, 2)$，就能确定 $[0, 2)$ 的和；反过来，如果已知 $[0, 1)$, $[0, 2)$，也能确定 $[1, 2)$ 的和。但如果仅已知 $[0, 2)$, $[2, 4)$ 则不能确定 $[0, 3)$ 或 $[1, 2)$ 的和。

由于答案很大，你需要输出答案对 $998244353$ 取模后的值。

---

输入格式

从文件 segtree.in 中读入数据。

输入的第一行包含两个整数 $N$, $M$，分别表示数组长度和区间个数。

输入的第二行包含 $N - 1$ 个整数 $X_1, X_2, \dots , X_{N-1}$。

接下来 $M$ 行，每行包含两个整数 $L_i$, $R_i$，表示一个区间。

---

输出格式

输出到文件 segtree.out 中。

输出一行一个整数表示答案对 $998244353$ 取模后的值。

---

样例 1

输入

2 1
1
0 2

输出

5

只有当直接知道 $[0, 2)$ 的总和或同时知道 $[0, 1)$ 和 $[1, 2)$ 的总和时才能知道 $[0, 2)$ 的总和，因此总的方案数为 $2^2 + 1 = 5$。

---

样例 2

输入

2 1
1 
1 2

输出

5

---

样例 3

输入

5 2
2 1 4 3
1 3
2 5

输出

193

---

样例 4

输入

10 10
5 2 1 3 4 7 6 8 9
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 10

输出

70848

---

数据范围与提示

对于所有测试数据：

• $2 \le N \le 2 \times 10^5$，
• $1 \le M \le \min \{\frac{N(N+1)}{2}, 2 \times 10^5\}$，
• $\forall 1 \le i \le N - 1, 1 \le X_i \le N - 1$，
• 保证 $X_i$ 正确描述了一棵线段树，
• $\forall 1 \le i \le M, 0 \le L_i < R_i \le N$，
• $\forall i \ne j,(L_i, R_i) \ne (L_j, R_j )$。

测试点	$N \leq$	$M$	特殊性质	测试点	$N \leq$	$M$	特殊性质
1	$3$	无额外限制	是	11	$2 \times 10^5$	$=2$	否
2	$10$		否	12		$=3$
3	$100$			13		$=4$
4				14		$=5$
5	$500$			15		无额外限制	是
6				16
7	$5,000$			17
8				18			否
9	$2 \times 10^5$	$=1$		19
10				20

特殊性质：保证 $M=N$, $L_i=0$, $R_i=i$。