In-order

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 (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, so that each team can have a distinct tree layout, calculate the number of different possible in-order traversals, $T$, modulo the prime number $999\,999\,937$.

The input consists of four lines. The first line contains the number $N$. Each of the next three lines contains $N$ space-separated integers.

The second line contains $A_1, A_2, \dots, A_N$, where $A_k$ is the number of the $k$th athlete in pre-order traversal.

The third line contains $B_1, B_2, \dots, B_N$, where $B_k$ is the number of the $k$th athlete in post-order traversal.

The fourth line contains $C_1, C_2, \dots, C_N$, where $C_k$ is the number of the $k$th athlete in in-order traversal, or $0$ if the organiser did not specify that athlete.

The output is a single line containing a single integer $S$, the only integer such that $0 \le S < 999\,999\,937$ and $T - S$ is divisible by $999\,999\,937$.

• $1 \le N \le 500\,000$
• There exists at least one binary tree with such pre-order, post-order, and in-order traversals.
• The indices $k$ for which $C_k \ge 1$ form a (possibly empty) sub-interval of $\{1, 2, \dots, N\}$. In other words, if $k \le \ell$ and both $C_k$ and $C_\ell$ are positive, then all of $C_k, C_{k+1}, \dots, C_\ell$ are positive.