Segment Tree Subset Determination

Consider an array (A) of length (N) whose values are unknown. A special segment tree is built on (A) as follows. The segment tree is a rooted binary tree where every node corresponds to an interval ([l,r)) (with (0 \le l < r \le N)). The root corresponds to ([0,N)). If (r-l=1) the node is a leaf; otherwise, there exists an integer (m) with (l < m < r) such that the left child represents ([l,m)) and the right child represents ([m,r)). Note that the shape of the tree may vary since the splitting point (m) for every non‐leaf node is chosen arbitrarily. In each node the tree maintains the sum (a_l+a_{l+1}+\cdots+a_{r-1}).

Now, you are given the array (X_1,X_2,\dots,X_{N-1}) which is the sequence of splitting points of the non‐leaf nodes in the (\textbf{preorder}) traversal of the segment tree. For example, for (N=5) and (X=[2,1,4,3]) the preorder traversal of all nodes is: ([0,5), [0,2), [0,1), [1,2), [2,5), [2,4), [2,3), [3,4), [4,5)).

The twist is that a person, say J, does not know any element of (A) but he does have the segment tree, that is, the values maintained in all its nodes, however only for some subset (S) of the nodes (each subset of nodes is obtained independently, and there are a total of (2^{2N-1}) possible such subsets).

J has (M) query intervals ([L_1,R_1), [L_2,R_2),\dots,[L_M,R_M)). He wants to count how many subsets (S) of the segment tree nodes have the following property:

For every query interval ([L,R)), the sum (a_L+\cdots+a_{R-1}) can be uniquely determined given the values in (S) (and using the relation that in any internal node, the stored value equals the sum of its two children). Note that even if the node corresponding exactly to ([L,R)) is not in (S), its value might be deduced by combining the values from the children. For example, if we know the values in ([0,1)) and ([1,2)) then we can deduce the sum in ([0,2)); conversely, if we know ([0,1)) and ([0,2)) then ([1,2)) is determined. However, knowing only ([0,2)) and ([2,4)) does not suffice to determine ([0,3)) or ([1,2)).

It turns out that one may show that a subset (S) determines the answer to all queries if and only if for every query ([L,R)) the following holds: when you decompose ([L,R)) into a unique set of disjoint tree nodes (by the standard segment tree query algorithm), then each node in the decomposition is either directly in (S) or, if not, then its value can be deduced because all the leaves in its subtree (which are the fundamental unknowns) are contained in (S).

Your task is to compute the number of subsets (S) (out of (2^{2N-1}) possible ones) that guarantee that every query interval sum is uniquely determined. As the answer can be huge, output it modulo (998244353).

inputFormat

The input is given as follows:

• The first line contains an integer (N) ((1 \le N \le 10)).
• The second line contains (N-1) integers: (X_1, X_2, \dots, X_{N-1}), representing the splitting points in the preorder of the non‐leaf nodes.
• The third line contains an integer (M) ((1 \le M \le 50)), the number of queries.
• Then (M) lines follow, each containing two integers (L_i) and (R_i) (with (0 \le L_i < R_i \le N)) representing a query interval ([L_i, R_i)).

outputFormat

Output a single integer --- the number of subsets (S) that determine every query interval sum, modulo (998244353).

sample

5
2 1 4 3
1
0 2

8