Problem Description

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

The definition of the segment tree in this problem may differ from the one 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 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 range sum problem, given a 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 of the numbers 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\) and \(X = [2, 1, 4, 3]\), 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 how many subsets \(S\) of the \(2^{2N-1}\) nodes in the segment tree 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), [1, 2)\) are known, the sum of \([0, 2)\) can be determined; conversely, if \([0, 1), [0, 2)\) are known, the sum of \([1, 2)\) can also be determined. However, if only \([0, 2), [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 both \([0, 1)\) and \([1, 2)\) are known can the sum of \([0, 2)\) be determined, thus 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)\).

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 restrictions.

见题面 Input 部分

见题面 Output 部分