最近，小 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} + \dots + 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)$ 的和无法确定。

由于答案可能非常大，你需要输出答案对 $998, 244, 353$ 取模的结果。

输入格式

第一行包含两个整数 $N$ 和 $M$ ($2 \le N \le 2 \times 10^5, 1 \le M \le \min\{\frac{N(N+1)}{2}, 2 \times 10^5\}$)。

第二行包含 $N - 1$ 个整数 $X_1, X_2, \dots, X_{N-1}$ ($1 \le X_i \le N - 1$，序列 $X_i$ 描述了一棵合法的线段树)。

接下来 $M$ 行描述了 $L_i$ 和 $R_i$ 的值 ($0 \le L_i < R_i \le N$)。第 $i$ 行包含两个整数 $L_i$ 和 $R_i$。

保证对于所有 $i \neq j$，$(L_i, R_i) \neq (L_j, R_j)$。

输出格式

输出一行一个整数，表示答案对 $998, 244, 353$ 取模的结果。

样例

样例输入 1

2 1
1
0 2

样例输出 1

5

样例输入 2

2 1
1
1 2

样例输出 2

5

样例输入 3

5 2
2 1 4 3
1 3
2 5

样例输出 3

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

样例输出 4

70848