중위 순회

올림픽 개막식은 배에 탄 팀들이 강 위에서 진행한다. 배 위 선수들의 배치는 특별한 방식으로 정해져 있다. 각 팀의 선수 $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$이다.

출력은 한 줄이며, 정수 $S$ 하나를 출력한다. $S$는 $0 \le S < 999\,999\,937$을 만족하고, $T - S$가 $999\,999\,937$로 나누어떨어지는 유일한 정수이다.

• $1 \le N \le 500\,000$
• 주어진 전위, 후위, 중위 순회를 모두 만족하는 이진 트리가 적어도 하나 존재한다.
• $C_k \ge 1$인 인덱스 $k$들은 (비어 있을 수도 있는) $\{1, 2, \dots, N\}$의 연속된 구간을 이룬다. 즉, $k \le \ell$이고 $C_k$와 $C_\ell$이 모두 양수이면 $C_k, C_{k+1}, \dots, C_\ell$도 모두 양수이다.