Segment tree is a data structure based on the divide-and-conquer algorithm, but this has nothing to do with this problem. It's just to make the title start with D.
For this problem, a segment tree is a perfect binary tree. A segment tree of depth $$$n$$$ has exactly $$$2^{n+1}-1$$$ nodes. Note that the root has depth $$$0$$$, so a segment tree of depth $$$n$$$ has $$$n+1$$$ levels.
To make the structure of a segment tree easier to describe, we assign indices to its nodes. The root is assigned index $$$1$$$. Every non-leaf node is assigned an index $$$k$$$ satisfying $$$1\leq k \lt 2^n$$$. It has exactly two children: its left child has index $$$2k$$$, and its right child has index $$$2k+1$$$.
Each node of a segment tree also has a value. Let $$$a_k$$$ denote the value of node $$$k$$$. For every non-leaf node $$$k$$$, its value $$$a_k$$$ must be the maximum of the values of its two children; that is, $$$$$$ a_k=\max\{a_{2k},a_{2k+1}\}. $$$$$$
The leaf nodes have indices $$$2^n,2^n+1,\ldots,2^{n+1}-1$$$, and their values must form a permutation of $$$1,2,\ldots,2^n$$$. In other words, the elements of the sequence $$$a_{2^n},a_{2^n+1},\ldots,a_{2^{n+1}-1}$$$ must be pairwise distinct integers, and $$$1\leq a_{2^n+i}\leq 2^n$$$ must hold for every $$$0\leq i \lt 2^n$$$.
There are now $$$q$$$ constraints. The $$$i$$$-th constraint is of the form $$$(u_i,x_i)$$$. Here, $$$u_i$$$ is a node index and $$$x_i$$$ is a specified value; the constraint requires the value $$$a_{u_i}$$$ of node $$$u_i$$$ to be equal to $$$x_i$$$. Calculate the number of segment trees satisfying all $$$q$$$ constraints, or equivalently, the number of distinct valid sequences $$$a_1,a_2,\ldots,a_{2^{n+1}-1}$$$. Output the answer modulo $$$998244353$$$.
The first line contains two integers $$$n$$$ $$$(1\le n\le 18)$$$ and $$$q$$$ $$$(0\le q\le 2^{n+1}-1)$$$.
Each of the next $$$q$$$ lines contains two integers $$$u_i$$$ $$$(1\le u_i \lt 2^{n+1})$$$ and $$$x_i$$$ $$$(1\le x_i\le 2^n)$$$, meaning that the value $$$a_{u_i}$$$ of node $$$u_i$$$ is required to be equal to $$$x_i$$$.
Output one integer: the number of valid leaf permutations modulo $$$998244353$$$.
2 12 2
4
2 21 42 4
12
2 22 34 4
0
4 21 21 3
0
In Example 1, the four valid segment trees are:
$$$$$$ \begin{aligned} \begin{array}{ccccccccccc} &&&&&4&&&&&\\[-0.2em] &&&\diagup&&&&\diagdown&&&\\[-0.2em] &&2&&&&&&4&&\\[-0.2em] &\diagup&&\diagdown&&&&\diagup&&\diagdown&\\[-0.2em] 1&&&&2&&3&&&&4\\ &&&&&\text{(1)}&&&&& \end{array} &\qquad\qquad \begin{array}{ccccccccccc} &&&&&4&&&&&\\[-0.2em] &&&\diagup&&&&\diagdown&&&\\[-0.2em] &&2&&&&&&4&&\\[-0.2em] &\diagup&&\diagdown&&&&\diagup&&\diagdown&\\[-0.2em] 1&&&&2&&4&&&&3\\ &&&&&\text{(2)}&&&&& \end{array} \\[2em] \begin{array}{ccccccccccc} &&&&&4&&&&&\\[-0.2em] &&&\diagup&&&&\diagdown&&&\\[-0.2em] &&2&&&&&&4&&\\[-0.2em] &\diagup&&\diagdown&&&&\diagup&&\diagdown&\\[-0.2em] 2&&&&1&&3&&&&4\\ &&&&&\text{(3)}&&&&& \end{array} &\qquad\qquad \begin{array}{ccccccccccc} &&&&&4&&&&&\\[-0.2em] &&&\diagup&&&&\diagdown&&&\\[-0.2em] &&2&&&&&&4&&\\[-0.2em] &\diagup&&\diagdown&&&&\diagup&&\diagdown&\\[-0.2em] 2&&&&1&&4&&&&3\\ &&&&&\text{(4)}&&&&& \end{array} \end{aligned} $$$$$$
The corresponding arrays are: $$$$$$ \begin{aligned} (a_1,a_2,\ldots,a_7)&=(4,2,4,1,2,3,4) &&\text{in (1)}\\ (a_1,a_2,\ldots,a_7)&=(4,2,4,1,2,4,3) &&\text{in (2)}\\ (a_1,a_2,\ldots,a_7)&=(4,2,4,2,1,3,4) &&\text{in (3)}\\ (a_1,a_2,\ldots,a_7)&=(4,2,4,2,1,4,3) &&\text{in (4)} \end{aligned} $$$$$$
Therefore, the answer is $$$4$$$.
In Example 2, the root always has value $$$4$$$, since $$$4$$$ is the maximum leaf value. The condition $$$a_2=4$$$ requires the leaf with value $$$4$$$ to be either node $$$4$$$ or node $$$5$$$. After choosing its position, the other three values can be placed arbitrarily, giving $$$2\times 3!=12$$$ valid leaf permutations.
In Example 3, $$$a_2=\max\{a_4,a_5\}$$$ must be at least $$$a_4=4$$$, so it cannot be equal to $$$3$$$. Thus, no valid leaf permutation exists.
In Example 4, the two constraints require $$$a_1$$$ to be both $$$2$$$ and $$$3$$$, which is impossible.
