P13804 [SWERC 2023] In-order

:::align{center}  ::: 奥运会的开幕式将在河上举行，运动员们将乘船出场。每支队伍的运动员在船上的排列方式被设计成一棵二叉树，每支队伍有 $N$ 名运动员（编号为 $1$ 到 $N$）。 组委会还为每支队伍指定了二叉树的先序遍历、后序遍历，以及中序遍历中的一个（可能为空）连续区间。 现在，为了确保有足够多的树形排列，使得每支队伍都能拥有独特的排列方式，你需要计算不同可能的中序遍历的数量 $T$，并对质数 $999\,999\,937$ 取模。

输入包含四行。第一行包含一个整数 $N$。接下来的三行每行包含 $N$ 个用空格分隔的整数。第二行为 $A_1, A_2, \dots, A_N$，其中 $A_k$ 表示先序遍历中第 $k$ 个运动员的编号。第三行为 $B_1, B_2, \dots, B_N$，其中 $B_k$ 表示后序遍历中第 $k$ 个运动员的编号。第四行为 $C_1, C_2, \dots, C_N$，其中 $C_k$ 要么是中序遍历中第 $k$ 个运动员的编号，要么为 $0$，表示组委会未指定第 $k$ 个运动员。 **数据范围** - $1 \leq N \leq 500\,000$； - 至少存在一棵二叉树，其先序、后序和中序遍历分别为所给序列； - 对于所有 $C_k \geq 1$ 的 $k$，这些 $k$ 构成集合 $\{1, 2, \dots, N\}$ 的一个（可能为空）连续子区间。换句话说，若 $k \leq l$ 且 $C_k, C_l$ 都大于 $0$，则 $C_k, C_{k+1}, \dots, C_l$ 都大于 $0$。

输出一行，包含一个整数 $S$，满足 $0 \leq S < 999\,999\,937$，且 $T-S$ 能被 $999\,999\,937$ 整除。

**样例解释 1** 题目上方给出的两棵二叉树的中序遍历分别为： - $5\ 3\ 6\ 2\ 4\ 8\ 7\ 1$ - $5\ 3\ 6\ 2\ 4\ 7\ 8\ 1$ **样例解释 2** 四种可能的中序遍历为： - $3\ 2\ 1$ - $2\ 3\ 1$ - $1\ 3\ 2$ - $1\ 2\ 3$ **样例解释 3** 三种可能的中序遍历为： - $2\ 4\ 3\ 1$ - $1\ 4\ 3\ 2$ - $3\ 4\ 2\ 1$ 由 ChatGPT 4.1 翻译