Problem Description

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

The following provides the definition of the segment tree used in this problem. This definition may differ from the segment tree you are familiar with.

• A segment tree is a rooted binary tree where each node corresponds to an interval \([l, r)\) on the sequence, with the root node corresponding to \([0, n)\).
• For each node, if the sequence interval \([l, r)\) it represents satisfies \(r - l = 1\), it is a leaf node; otherwise, there exists an integer \(m\) (\(l < m < r\)) such that its left child represents the interval \([l, m)\) and its right child represents the interval \([m, r)\).
• The structure of the segment tree depends on the choice of the split point \(m\) for each non-leaf node.
• For the problem of range sum queries on 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 of length \(N\), \(A_0, A_1, \dots, A_{N-1}\), and he does not know any of the numbers in \(A\). However, he has a segment tree that maintains the interval 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\) and \(X = [2, 1, 4, 3]\), the preorder traversal of the segment tree nodes includes \([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 \(2^{2N-1}\) subsets of 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 of each interval \([L_i, R_i)\) can be uniquely determined.

For example, if \([0, 1)\) and \([1, 2)\) are known, the sum of \([0, 2)\) can be determined; conversely, if \([0, 1)\) and \([0, 2)\) are known, the sum of \([1, 2)\) can also be determined. However, if only \([0, 2)\) and \([2, 4)\) are known, the sums 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 of input contains two integers \(N\) and \(M\), representing the length of the array and the number of intervals, respectively.

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\) and \(R_i\), representing an interval.

Output Format

Output a single integer representing the answer modulo \(998244353\).

Sample Input and Output

Sample Input #1

2 1
1
0 2

Sample Output #1

5

Sample Input #2

2 1
1
1 2

Sample Output #2

5

Sample Input #3

5 2
2 1 4 3
1 3
2 5

Sample Output #3

193

Sample Input #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

Sample Output #4

70848

Notes/Hints

Sample 1 Explanation

Only when the sum of \([0, 2)\) is directly known or when the sums of both \([0, 1)\) and \([1, 2)\) are known can the sum of \([0, 2)\) be determined. Therefore, the total number of solutions is \(2^2 + 1 = 5\).

Data Range

For all test data:
- \(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\),
- The \(X_i\) correctly describe 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)\).

见题面 Input 部分

见题面 Output 部分