Problem Description

Little Y has recently learned how to use a segment tree to maintain a sequence and support range sum queries.

Below is the definition of the segment tree used in this problem. This definition may be different from the segment tree you are familiar with.

• A segment tree is a rooted binary tree. Each node corresponds to an interval $[l, r)$ on the sequence, where the root corresponds to $[0, n)$.
• For each node, if its interval $[l, r)$ satisfies $r - l = 1$, then it is a leaf node. Otherwise, there exists an integer $m(l < m < r)$ such that its left child represents $[l, m)$ and its right child represents $[m, r)$.
• The shape of the segment tree depends on the choice of the split point $m$ for each non-leaf node.
• For the range sum problem, for the sequence $a_0, a_1, \dots, a_{n-1}$, each node $[l, r)$ in the segment tree maintains the value of $(a_l + a_{l+1} + \cdots + a_{r-1})$.

Little J has an array of length $N$, $A_0, A_1, \dots, A_{N-1}$. He does not know any value in $A$, but he has a segment tree that maintains the range sums of $A$. The segment tree is given by $X_1, X_2, \dots, X_{N-1}$, where $X_i$ is the split point of the $i$-th non-leaf node in the preorder traversal of the segment tree.

For example, if $N = 5, X = [2, 1, 4, 3]$, then the nodes in the segment tree, in preorder traversal, are $[0, 5), [0, 2), [0, 1), [1, 2), [2, 5), [2, 4), [2, 3), [3, 4), [4, 5)$.

Little J has $M$ intervals $[L_1, R_1), [L_2, R_2), \dots, [L_M, R_M)$. He wants to know: among all subsets $S$ of the $2N - 1$ segment tree nodes, how many subsets $S$ satisfy the following condition:

• If the values maintained by all nodes in $S$ are known, then the sum over each interval $[L_i, R_i)$ can be uniquely determined.

For example, if $[0, 1)$ and $[1, 2)$ are known, then the sum over $[0, 2)$ can be determined. Conversely, if $[0, 1)$ and $[0, 2)$ are known, then the sum over $[1, 2)$ can also be determined. But if only $[0, 2)$ and $[2, 4)$ are known, then the sum over $[0, 3)$ or $[1, 2)$ cannot be determined.

Since the answer can be very large, you need to output the answer modulo $998244353$.

Input Format

The first line contains two integers $N, M$, representing the array length and the number of intervals.

The second line contains $N - 1$ integers $X_1, X_2, \dots, X_{N-1}$.

The next $M$ lines each contain two integers $L_i, R_i$, representing an interval.

Output Format

Output one line with one integer, representing the answer modulo $998244353$.

2 1
1
0 2

5

2 1
1 
1 2

5

5 2
2 1 4 3
1 3
2 5

193

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

Hint

Explanation for Sample 1

Only when you directly know the total sum of $[0, 2)$, or when you know both the total sums of $[0, 1)$ and $[1, 2)$, can you determine the total sum of $[0, 2)$. Therefore, the total number of valid choices is $2^2 + 1 = 5$.

Constraints

For all testdata:

• $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$.
• It is guaranteed that $X_i$ correctly describes a segment tree.
• $\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)$.

Subtask 1 (6 points): $N \le 10$.

Subtask 2 (18 points): $N \le 100$.

Subtask 3 (9 points): $N \le 500$.

Subtask 4 (17 points): $N \le 5000$.

Subtask 5 (10 points): $M = 1$.

Subtask 6 (13 points): $M \le 5$.

Subtask 7 (7 points): $M = N, L_i = 0, R_i = i$.

Subtask 8 (20 points): No additional constraints.

Translated by ChatGPT 5