题目描述

:::align{center}

:::

The opening ceremony for the Olympic Games will take place on the river with teams on boats. The layout of the athletes on top of the boat has been designed in a very specific way: for each team, the $N$ athletes (conveniently numbered from 1 to $N$) are arranged as a binary tree.

The organiser has also designed the pre-order traversal, post-order traversal, and a (possibly empty) consecutive part of the in-order traversal of the binary tree that each team must follow.

Now, to make sure there are enough tree layouts so that each team can have a distinct one, you are asked to calculate the quantity of different possible in-order traversals, say $T$, modulo the prime number $999~999~937$.

输入格式

The input consists of four lines. The first line contains the number $N$. Each subsequent line contains a list of $N$ space-separated integers. The second line contains a list $A_1, A_2, \dots, A_N$, where $A_k$ is the number of the $k^\text{th}$ athlete found in pre-order traversal. The third line contains a list $B_1, B_2, \dots, B_N$, where $B_k$ is the number of the $k^\text{th}$ athlete found in post-order traversal. The fourth line contains a list $C_1, C_2, \dots, C_N$, where $C_k$ is either the number of the $k^\text{th}$ athlete found in in-order traversal, or 0 if the organiser did not say who that $k^\text{th}$ athlete should be.

Limits

• $1 \leq N \leq 500~000$;
• there exists at least one binary tree with such pre-order, post-order and in-order traversals;
• the integers k for which $C_k \geq 1$ form a (possibly empty) sub-interval of the set $\{1, 2, \dots, N\}$; in other words, whenever $k \leq l$ and both $C_k$ and $C_l$ are positive, all the integers $C_k, C_{k+1}, \dots, C_l$ are positive.

输出格式

The output should contain a single line, consisting of a single integer $S$: this is the only integer such that $0\leq S < 999~999~937$ and for which $T-S$ is divisible by $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

提示

Sample Explanation 1

The graphs given above the problem statement are the two possible binary trees. Their in-order traversals are:

• $5\ 3\ 6\ 2\ 4\ 8\ 7\ 1$
• $5\ 3\ 6\ 2\ 4\ 7\ 8\ 1$

Sample Explanation 2

The four possible in-order traversals are:

• $3\ 2\ 1$
• $2\ 3\ 1$
• $1\ 3\ 2$
• $1\ 2\ 3$

Sample Explanation 3

The three possible in-order traversals are:

• $2\ 4\ 3\ 1$
• $1\ 4\ 3\ 2$
• $3\ 4\ 2\ 1$