AT_nyc2015_9.マージ

すぬけ君打算将两个数组 $P$ 和 $Q$ 合并成一个新的数组 $R$。

合并过程如下：

• 初始状态下，$R$ 是一个空数组。
• 在 $P$ 或 $Q$ 至少有一个不为空的情况下，从中选择一个非空的数组（若两个数组都非空，则可以任选其一），然后取出该数组的第一个元素，将其添加到数组 $R$ 的末尾。

现在给定两个数组 $P$ 和 $Q$，它们都是从 $1$ 到 $N$ 的排列。请你计算出可以生成多少种不同的 $R$ 的方式，结果对 $1,000,000,007$ 取模。

输入格式

输入通过标准输入给出，格式如下：

N
P_1 P_2 ... P_N
Q_1 Q_2 ... Q_N

输出格式

输出一个整数，表示生成的不同数组 $R$ 的个数，对 $1,000,000,007$ 取模。

数据范围

• $1 \leq N \leq 2000$
• $P$ 和 $Q$ 都是从 $1$ 到 $N$ 的一个排列。

示例

输入

4
3 1 2 4
3 1 2 4

输出

14

输入

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

输出

127224

以上即为题目的详细描述。通过这种合并方式，找出每一种可能的组合排列数，然后输出对 $1,000,000,007$ 取模的结果。

本翻译由 AI 自动生成