Unique Interval Sum Determination

Consider an array (A_0, A_1, \dots, A_{N-1}) that is maintained by a segment tree defined as follows:

• A segment tree is a rooted binary tree. Each node corresponds to an interval \([l, r)\) of indices. The root corresponds to \([0, N)\).
• If a node corresponds to an interval \([l, r)\) with \(r-l=1\), it is a leaf; otherwise, there is an integer \(m\) satisfying \(l < m < r\) (the choice of \(m\) may vary) such that the left child represents \([l, m)\) and the right child represents \([m, r)\).
• In this tree the structure depends on the choice of the division points. In this problem the tree is uniquely determined by the pre‐order sequence \(X_1, X_2, \dots, X_{N-1}\), where \(X_i\) is the division point of the \(i\textth non–leaf node encountered in a pre–order traversal.
• For a given array \(A\) the value maintained at any node corresponding to \([l, r)\) is \[ A_l + A_{l+1} + \cdots + A_{r-1} \] (in \(\LaTeX\) we write \(\sum_{i=l}^{r-1} A_i\)).

Now, suppose someone knows nothing about the values of (A) but holds the segment tree that maintains the interval sums. Instead of every node’s value, a subset (S) of the (2N-1) nodes is revealed. Thanks to the fact that for every non–leaf node the following relation holds

[ \text{parent} = \text{left child} + \text{right child}, ]

it may be possible to deduce the values of some non–revealed nodes from the revealed ones. In particular, we say that the value at a node is determined if:

• If the node is a leaf, its value is determined if and only if it is in \(S\).
• If the node is internal (i.e. it has children), its value is determined if either it is in \(S\) or both of its children’s values are determined (in which case the value can be deduced from the sum of the children).

For example, if the revealed set is (S = {[0,1), [1,2)}) then the sum over ([0,2)) is determined since ([0,2) = [0,1)+[1,2)). Similarly, if (S = {[0,1), [0,2)}) then the value for ([1,2)) is determined as ([1,2) = [0,2) - [0,1)). However, if (S = {[0,2), [2,4)}) then one cannot uniquely determine the sum on ([0,3)) or ([1,2)).

Finally, you are given (M) query intervals ([L_1,R_1), [L_2,R_2), \dots, [L_M,R_M)). We say the set (S) is good if, knowing the values in (S) together with the tree structure and the relation of the parent with its children, the sum on each query interval can be computed uniquely. In other words, for every query interval ([L, R)) the following holds: There is a way to decompose ([L,R)) as a disjoint union of node intervals that are determined (possibly indirectly via the recurrence), so that the sum over ([L,R)) is computed uniquely.

Your task is to count the number of subsets (S) of the tree nodes (there are (2^{2N-1}) subsets in total) such that (S) is good. Output the answer modulo (998244353).

Input/Output format:

• Input: The first line contains two integers \(N\) and \(M\). The second line contains \(N-1\) integers \(X_1, X_2, \dots, X_{N-1}\) representing the pre–order division points of the non–leaf nodes. Each of the next \(M\) lines contains two integers \(L\) and \(R\) representing a query interval \([L, R)\) (with \(0 \le L < R \le N\)).
• Output: Output one integer – the number of good subsets \(S\) modulo \(998244353\).

Note: Some intervals in the queries may not correspond to a node in the tree. However, by decomposing the query interval into a disjoint union of (determined) node intervals (using the recurrence relation), its sum might still be uniquely determined.

Example:

For example, if \(N = 5\) and \(X = [2, 1, 4, 3]\), then one possible traversal of the tree is:

[0,5), [0,2), [0,1), [1,2), [2,5), [2,4), [2,3), [3,4), [4,5)

If the queries are ([0,2)) and ([2,5)), one can verify that a revealed set (S) which contains, for instance, ([0,1)), ([1,2)), ([2,4)) and ([4,5)) is good, while some other choices are not. (In the sample, the answer happens to be 210.)

inputFormat

The first line contains two integers (N) and (M). The second line contains (N-1) integers (X_1, X_2, \dots, X_{N-1}). Then (M) lines follow, each with two integers (L) and (R), representing the query interval ([L,R)).

outputFormat

Output a single integer: the number of good subsets (S) modulo (998244353).

sample

5 2
2 1 4 3
0 2
2 5

210