Snuke 想要通过合并两个数组 $P$ 和 $Q$ 来创建一个数组 $R$。形式上，数组 $R$ 是通过以下方式获得的：

• 初始时，数组 $R$ 为空。
• 当 $P$ 和 $Q$ 中至少有一个非空时，选择一个非空数组（$P$ 或 $Q$），弹出其最左侧的元素，并将其附加到 $R$ 的末尾。

给定 $P$ 和 $Q$，它们分别是 $1, \dots, N$ 的排列。计算 Snuke 可以创建的可能的不同数组的数量，并将答案对 $10^9 + 7$ 取模。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 2000$)。第二行包含 $N$ 个整数 $P_i$ ($1 \le P_i \le N, P_i \neq P_j$ 当 $i \neq j$ 时)。第三行包含 $N$ 个整数 $Q_i$ ($1 \le Q_i \le N, Q_i \neq Q_j$ 当 $i \neq j$ 时)。

输出格式

在一行中打印答案。

样例

样例输入 1

4
3 1 2 4
3 1 2 4

样例输出 1

14

样例输入 2

10
5 7 3 1 6 4 2 10 9 8
2 8 9 1 5 6 10 4 3 7

样例输出 2

127224