一棵 $2^{N+1}-1$ 点的满二叉树，为节点赋权值 $a_k$，满足：

• 叶子权值为 $(1, 2, \dots, 2^N)$ 的一个 permutation；
• 非叶子满足 $a_k = \max(a_{2k}, a_{2k+1})$；
• $Q$ 条限制 $a_{u_i} = X_i$。

求满足所有限制的 $a$ 的数量。

首先特判：同一个点的权值冲突；或不满足 $a_k = \max(a_{2k}, a_{2k+1})$。

以下只需要考虑 permutation 的约束。

考虑每个权值 $x$。由于 $x$ 在叶子中只出现一次，因此所有满足 $a_{u}=x$ 的节点 $u$ 在 同一条祖先链 上，否则无解。设这些 $u$ 中，最浅的是 $u_{\min}$，最深的是 $u_{\max}$，那么

• $u_{\min}$ 子树内所有叶子都满足权值 $\leqslant x$。
• 数值 $x$ 所在的叶子必须放在 $u_{\max}$ 的子树里，这些节点都是候选。

基于这两条限制，从祖先向叶子传递约束，便能够得到每个叶子「是否是 $x$ 的候选」和「最大能填多少」，并统计对应的数量：$x$ 的 候选的叶子数量 $c_x$ 和 最大能填 $x$ 的叶子数量 $v_x$ 。

按照数值从大到小依次确定每个数 $x$ 填在哪个叶子上：

• 如果权值 $x$ 在题目限制中出现过，那么选择方案数是 $x$ 的候选的叶子数量 $c_x$，置 $\text{Ans} \gets \text{Ans} \times c_x$；
• 否则，选择方案数是目前所有「最大能填 $y$ ($y \geqslant x$)」的叶子总数，可以动态维护这些叶子数量，每次置 $\text{Ans} \gets \text{Ans} \times S$，并更新 $S \gets S + v_x - 1$。

以上都可以用若干次循环解决，复杂度 $\mathcal{O}(Q+2^{N})$。