奥运会开幕式将在河上举行，各代表队乘坐船只。船上运动员的布局设计得非常独特：对于每支代表队， $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$ 个运动员的编号，如果组织者没有指定第 $k$ 个运动员是谁，则为 $0$。

输出格式

输出应包含一行，即一个整数 $S$：这是满足 $0 \leqslant S < 999\,999\,937$ 且 $T - S$ 能被 $999\,999\,937$ 整除的唯一整数。

数据范围

• $1 \leqslant N \leqslant 500\,000$；
• 保证至少存在一棵符合给定先序、后序和中序遍历的二叉树；
• $C_k \geqslant 1$ 的整数 $k$ 构成集合 $\{1, 2, \dots, N\}$ 的一个（可能为空的）子区间；换句话说，只要 $k \leqslant \ell$ 且 $C_k$ 和 $C_\ell$ 均为正数，则所有整数 $C_k, C_{k+1}, \dots, C_\ell$ 均为正数。

样例

样例输入 1

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

样例输出 1

2

说明 1

题目描述上方的图示即为两种可能的二叉树。它们的中序遍历分别为： 5 3 6 2 4 8 7 1 5 3 6 2 4 7 8 1

样例输入 2

3
1 2 3
3 2 1
0 0 0

样例输出 2

4

说明 2

四种可能的中序遍历为： 3 2 1 2 3 1 1 3 2 1 2 3

样例输入 3

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

样例输出 3

3

说明 3

三种可能的中序遍历为： 2 4 3 1 1 4 3 2 * 3 4 2 1