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 differ from the one you are familiar with.

• A segment tree is a rooted binary tree. Each node corresponds to an interval $[l, r)$ on the sequence, and 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 corresponds to $[l, m)$ and its right child corresponds to $[m, r)$.
• The shape of the segment tree depends on the choice of the split point $m$ for each non-leaf node.
• For range sum problems, for the sequence $a_0, a_1, \dots, a_{n-1}$, each node $[l, r)$ in the segment tree maintains the value $(a_l + a_{l+1} + \cdots + a_{r-1})$.

Little J has an array $A_0, A_1, \dots, A_{N-1}$ of length $N$. 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 preorder traversal of the nodes in the segment tree is $[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 of the $2N - 1$ segment tree nodes, how many subsets $S$ satisfy the following condition:

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

For example, if $[0, 1)$ and $[1, 2)$ are known, then the sum of $[0, 2)$ can be determined. Conversely, if $[0, 1)$ and $[0, 2)$ are known, then the sum of $[1, 2)$ can also be determined. But if only $[0, 2)$ and $[2, 4)$ are known, then the sum of $[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 integer in one line, 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 sums of $[0, 1)$ and $[1, 2)$ at the same time, can you determine the sum of $[0, 2)$. Therefore, the total number of valid ways 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)$.

Translated by ChatGPT 5