Description

:::align{center}

:::

奥运会的开幕式将在河上举行，运动员们将乘船出场。每支队伍的运动员在船上的排列方式被设计成一棵二叉树，每支队伍有 $N$ 名运动员（编号为 $1$ 到 $N$）。

组委会还为每支队伍指定了二叉树的先序遍历、后序遍历，以及中序遍历中的一个（可能为空）连续区间。

现在，为了确保有足够多的树形排列，使得每支队伍都能拥有独特的排列方式，你需要计算不同可能的中序遍历的数量 $T$，并对质数 $999\,999\,937$ 取模。

Input Format

输入包含四行。第一行包含一个整数 $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$。

Output Format

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

8
1 2 3 5 6 4 7 8
5 6 3 8 7 4 2 1
0 0 6 2 4 0 0 0

2

3
1 2 3
3 2 1
0 0 0

4

4
1 2 3 4
4 3 2 1
0 4 0 0

3

Hint

样例解释 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 翻译