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

The definition of a segment tree in this problem is provided below. 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)$ of 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)$.
  • Note that the structure of the segment tree depends on the choice of the partition point $m$ for each non-leaf node.
• Regarding range sum queries, for a sequence $a_0, a_1, \ldots, a_{n-1}$, each node $[l, r)$ in the segment tree maintains the value $\left(a_l+a_{l+1}+\cdots+a_{r-1}\right)$.

Little J has an array $A_0, A_1, \ldots, 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, \ldots, X_{N-1}$, where $X_i$ is the partition 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 contained 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), \ldots, [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, 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 be determined. However, if only $[0, 2)$ and $[2, 4)$ are known, the sum of $[0, 3)$ or $[1, 2)$ cannot be determined.

Since the answer is large, you need to output the answer modulo $998,244,353$.

Input

Read data from standard input.

The first line contains two integers $N, M$.

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

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

Output

Output to standard output.

Output a single integer representing the answer modulo $998,244,353$.

Examples

Input

2 1
1
0 2

Output

5

Note

The sum of $[0, 2)$ can only be determined if the sum of $[0, 2)$ is known directly, or if both the sums of $[0, 1)$ and $[1, 2)$ are known. Therefore, the total number of schemes is $2^2+1=5$.

Input

2 1
1
1 2

Output

5

Input

5 2
2 1 4 3
1 3
2 5

Output

193

Input

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

Output

70848

This test case satisfies special properties.

Subtasks

For all test data:

• $2\le N\le 2 \times 10^{5}$
• $1\le M\le \min\left\{\frac{N(N+1)}{2},2 \times 10^{5}\right\}$
• $\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 5\,000$.

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.