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 自动生成**

无

无

### Constraints すぬけ君は、配列 $ P $ と $ Q $ をマージして配列 $ R $ を作ることにした。 - 最初に、$ R $ は空である。 - $ P $ または $ Q $ が空でない間、$ P $ または $ Q $ のうち空でない配列 (両方空でない場合は好きなほう) を選び、その配列の左端の要素を取り出し、$ R $ の右端にくっつける。 $ P $, $ Q $ が与えられたとき、$ R $ としてできる配列が何通り考えられるか、$ \rm{mod}\ 1,000,000,007 $ で求めよ。 ただし、$ P $, $ Q $ はそれぞれ $ 1 $ から $ N $ の順列になっている。 - - - - - - - $ 1\ \leq\ N\ \leq\ 2000 $ - $ P,\ Q $ は $ 1 $ から $ N $ の順列である。